You are not logged in.
scratch that. i messed up again
cool! thanks
i have a small function i wrote in my personal math library.
def pair_coprime(numberlist):
for x in numberlist:
for y in xrange(len(numberlist)):
if x != numberlist[y]:
out = gcd(x,numberlist[y])
if out != 1:
return False #Some values are not coprime
return True #List is pairwise coprimeit could be faster, i think, but for now, its alright
i have another question:
can (a^b * c^d) mod e be done as [(a^b mod e) * (c^d mod e)] mod e? if not, whats an efficient way to do this on a computer? the exponentiation by squaring thing will still go through the second equation
interesting...
i think i found another way: im going to get a random number and add 1 until the value is coprime to k
yes, but what if the upper limits are large?
do you know java?
http://liris.cnrs.fr/~ohasan/pprs/paillierdemo/Paillier.java
Thanks! now... how do i chose random integers from the set? i cant list out all the possible values every time. the O(n) would be ridiculous
the z, but this one also has a * next to it
quick thing: what does it mean when a integer symbol has a little star next to it? i cant seem to remember and cant think of how to search for it
im trying to write the Paillier cryptosystem. it seems easy enough, but its not working for some reason or another
Thanks
edit: okay. i fail. i reversed the values. sorry for wasting your time
im trying to get the value of mu as shown in the stuff below, but im getting a completely different value
from http://liris.cnrs.fr/~ohasan/pprs/paillierdemo/index.html?pt1=10&pt2=21 (dont bother going there. the values change everytime)
# Select two random and distinct primes p and q of length k/2
p = 33581 <-- given
q = 53299 <-- given# Compute n = p*q
n = 1789833719 <-- got this# Compute lambda = lcm(p-1,q-1) = (p-1)*(q-1) / gcd(p-1,q-1)
lambda = 894873420 <-- got this# Select a random integer g in Z*_{n^2}
g = 3082513844323755387 <-- given# Compute mu = (L(g^lambda mod n^2))^-1 mod n, where L(u) = (u-1)/n <-- im getting the inside stuff to be 1323971239912197708, L(u) = 739717453
mu = 1430230768
im getting mu to be 148619716. yet, the values produced work, while mine dont. what am i doing wrong?
darn.
yeah. just testing if the number is prime
is there a better and faster method of testing?
I think the bottleneck is the testing itself. Oh well. No matter. I'll eventually figure this out.
Thanks bobbym
yep, which is why i want to try to speed up the testing a bit
no. i guess my comment was a bit vague
i might as well put the real code:
p = randint(3, 2**L)
p = q * (1 + p/q) + 1
while MillerRabin(p) == False: # prime = True, composite = False
p = p + qmiller rabin is not what im creating. rather, it is another function that im using to test my p values, and it is the probabilistic test.
the L value can be 1024,2048, or 3072
well the entire code block is just a pseudo code, but randint (which is also a legitimate command) is supposed to returns a random integer between a and b, inclusive. the real code is barely any different
given:
Choose an L-bit prime modulus p such that p1 is a multiple of q.
what is the best way to find p that is both prime and (p-1) mod q = 0? right now, im doing the brute force way of:
q is some big prime number
p = randint(3,2^L) # i guess the bit size can be ignored for the moment
p = q * (1 + p/q) + 1 # since the values are ints, p/q is really floor(p/q). this gets a value that is a (multiple of q) +1, like q = 7 ->p = 3*7 +1 = 22
while p is not prime: # the testing function is MillerRabin
p = p - qtesting is taking forever, but since im terrible at reading other people's codes, ive been unable to find out how other people programed this to work very fast
Thanks for your help bobbym
i finally figured it out:
change r to little endian
do the equation i put in the first post
add the little endian of AES_k(n) and mod 2^128
change to little endian
oh. whoops. i forgot to change r to little endian. wow. i fail
edit:
what an annoying person. this guy changes the values to little endian so many times its not even funny
nope.
im looking at this other guy's code, and somehow he's getting the correct answer even though it looks like im doing the same thing as he is:
tot = 0
for i in range(q):
sub = msg[i*16 : i*16+16] + "\x01" # [backwards(0124bcb676f4f39395d883fb0f19ea3c66), backwards( 01366165d05266af8cdb6aa27e1079e6d7)]
sub += (17 - len(sub)) * "\x00"
num = str2num_littleend(sub) # c1 = 0x124bcb676f4f39395d883fb0f19ea3c66, c2 = 0x1366165d05266af8cdb6aa27e1079e6d7
tot = (tot + num) * rval # same as c1 * r^q + c2 * r^(q-1)+ ... cq*r right?
tot = tot % mod1305ooohhh... maybe. i'll check