generating the exponents in the first place

Forum Attachments

generating the exponents in the first place

calccrypto 26 Jul 2009 00:44

is there any way to generate prime numbers without really testing them? i read the rsa page, but python doesnt have any sort of prime number tester, and the largest number it will do 'for' on is 99,999,999. 'while' doesnt work because python cant divide for life. any suggestions?

how do other people generate the large numbers? how to the prime number generator functions work in java/c++/etc ?
where do you get one of the prime numbers in the first place?

oh yeah! i stumped dr.math. all the replier did was tell me to go to wikipedia

---

Visit Calccrypto for info on crypto
KC2ZOF

Last edited on 26 Jul 2009 01:07 by calccrypto Show more

Re: generating the exponents in the first place

builderboy 26 Jul 2009 03:37

The fastest way I know of is this

Create a list with numbers ranging from 1 all the way to your upper bound.
Remove every number divisible by 2 except the first.
Remove every number divisible by 3 except the first.
Remove every number divisible by 4 except the first.
…
repeat until you get to the square root of your upper bound, rounded up.

This is the fastest way I know of, and i spent quite some time with an obsession with calculating prime numbers on a calc. :P With this algorithm the 84SE could calculate all the prime numbers from 1 to 999 within 18 seconds.

Re: generating the exponents in the first place

thornahawk 26 Jul 2009 03:58

That is the sieve you are alluding to; that can of course be speeded up by considering only the odd numbers.

thornahawk

Re: generating the exponents in the first place

builderboy 26 Jul 2009 04:45

true, but then you miss 2, which is defined to be prime o.o

Re: generating the exponents in the first place

calccrypto 26 Jul 2009 04:50

im actually doing this in python

---

Visit Calccrypto for info on crypto
KC2ZOF

Re: generating the exponents in the first place

builderboy 26 Jul 2009 04:58

Ugh. Does python have things like arrays? I am completely unfamiliar with it, so I can't be of much help.

Last edited on 26 Jul 2009 04:58 by builderboy Show more

Re: generating the exponents in the first place

jnesselr 26 Jul 2009 05:15

In python, they are called lists.

Re: generating the exponents in the first place

calccrypto 26 Jul 2009 05:18

me neither.

---

Visit Calccrypto for info on crypto
KC2ZOF

Re: generating the exponents in the first place

thornahawk 26 Jul 2009 06:35

Hence you explicitly take 2 into account, e.g. this.

thornahawk

Re: generating the exponents in the first place

calccrypto 26 Jul 2009 15:14

its not that your program is useless, but that just gets tedious when calculating values that are 128+ bit in length

---

Visit Calccrypto for info on crypto
KC2ZOF

Re: generating the exponents in the first place

thornahawk 26 Jul 2009 15:35

That was actually meant more as an answer to "but then you miss 2, which is defined to be prime o.o" :) Of course the sieve is no longer the best approach for generating huge prime numbers (and it is pointless to use sieve-range primes for crypto purposes anyway); that's why the suggestion for incrementing upwards from a lower bound while testing for primality was given.

thornahawk

Re: generating the exponents in the first place

calccrypto 26 Jul 2009 15:50

oh. yeah. i forgot about that post

---

Visit Calccrypto for info on crypto
KC2ZOF

Re: generating the exponents in the first place

DarkerLine 26 Jul 2009 03:41

If I really wanted a large prime, I would use Mathematica or something like that. I don't think this is what you're looking for as an answer.

Here's a reasonable approach.

First, pick a range of numbers that are all as high as you want the primes to be. The prime number theorem says that if you're looking for 128-bit primes, then in an interval of 128, there's about 1.44=1/ln(2) primes. We want to be more or less certain we find a prime in this range, so let's take an interval of 7 times that length, where we expect there to be about 10 primes.

To weed out the majority of them, we test them for divisibility by small primes: 2, 3, 5, 7, etc. How many small primes is up to you.

Now, we implement some sort of probabilistic primality test. Miller-Rabin should be easy (look at the pseudocode: the only part of that you might have trouble with is the powers mod n, but we've already discussed how to do that). We test all the numbers that are left until we find some that are probably prime.

Re: generating the exponents in the first place

thornahawk 26 Jul 2009 03:56

What Mathematica actually uses to generate large primes (e.g. the NextPrime[] command) is to start incrementing after a pre-set lower bound and test until it hits a prime number, at least according to the code I've seen. There are a few other small details, but that essentially is the approach.

The primality test that would be easiest to implement would be Miller-Rabin (there is also a pseudocode implementation in the excellent (under construction!) work "Matters Computational" by Jorg Arndt, go search for it).

thornahawk

Re: generating the exponents in the first place

calccrypto 26 Jul 2009 04:52

i'll try it

---

Visit Calccrypto for info on crypto
KC2ZOF

Re: generating the exponents in the first place

calccrypto 26 Jul 2009 18:39

dont bother looking at this. i figured it out

hm… why is this code not working? its the same code as extgcd (i think), basically. i got this from wikipedia, which got it from "applied cryptography", so it shouldnt be wrong.

#Extended Euclidean Algorithm.
# for finding d
def findvalue(a,b):
    x = 0
    y = 1
    lastx = 1
    lasty = 0
    while b !=0:
        quotient = a/b
        temp = b
        b = a%b
        a = temp
        temp = x
        x = lastx-quotient*x
        lastx = temp
        temp = y
        y = lasty-quotient*y
        lasty = temp
    del x,y,lastx,temp,quotient,b,a
    return otherkey #(the other outputs are irrelevant and were deleted on the previous line)

some of the values it returns are the (mod value -1)

such as:

a = 804698291511391547869922453424169239319
b = 474462361710727340781151244583592066117

returns

c = 88722997661819588976540036373917984096

in which

the value of the bc mod a is 804698291511391547869922453424169239318, or (a -1)

now, the numbers are correct, but the computer is saying the output values before changing them to ASCII, are large than 256

---

Visit Calccrypto for info on crypto
KC2ZOF

Last edited on 26 Jul 2009 18:53 by calccrypto Show more

Re: generating the exponents in the first place

thornahawk 26 Jul 2009 18:59

What exactly are you using the extended Euclidean algorithm for, computing the modular inverse? There is no reference of the variable otherkey in the snippet you posted except in the last line.

thornahawk

Re: generating the exponents in the first place

calccrypto 26 Jul 2009 19:12

oh. i edited that by mistake. i changed the code a bit in my file and forgot to change some of it here. it turns out the error was in another file.

and yes, i was computing the inverse value

now, the main program seems to be forgetting to mod the values as it goes along, even though i never changed that bit of the code

---

Visit Calccrypto for info on crypto
KC2ZOF

Last edited on 26 Jul 2009 19:13 by calccrypto Show more

Re: generating the exponents in the first place

thornahawk 26 Jul 2009 19:21

Well, seeing that you merely need modular inversion, I had posted in a previous thread of yours a modified extended GCD algorithm; that might be a tidier choice than the extended Euclidean algorithm proper. Just replace the lines like

int(M/A)→U
M–AU→C

with something like

U=M div A
C=M mod A

as appropriate to the language you're using.

thornahawk

Re: generating the exponents in the first place

calccrypto 26 Jul 2009 19:50

hm… isnt it still basically the Euclidean algorithm?
i see now

---

Visit Calccrypto for info on crypto
KC2ZOF

Last edited on 26 Jul 2009 20:31 by calccrypto Show more

Re: generating the exponents in the first place

calccrypto 26 Jul 2009 20:18

hm… something' not right… now the values are correct and everything, but the modded values are not. shouldnt e*d mod m(or n) = 1? yet the stuff on wikipedia is giving large numbers that are no where close to 1

---

Visit Calccrypto for info on crypto
KC2ZOF

Last edited on 26 Jul 2009 20:42 by calccrypto Show more

Re: generating the exponents in the first place

calccrypto 26 Jul 2009 21:21

im totally lost right now. if ed = 1 mod m, then ed mod m = 1 right? and yet neither is wikipedia's values working at all, and the working values dont seem to fit the equation

---

Visit Calccrypto for info on crypto
KC2ZOF

Re: generating the exponents in the first place

calccrypto 27 Jul 2009 01:19

help please. im getting really frustrated because for every method i try, i get a different answer. i try my "e"s and "m"s both ways to make sure i didnt put them in the wrong places, and i have not gotten any 2 same answers yet

---

Visit Calccrypto for info on crypto
KC2ZOF

Re: generating the exponents in the first place

thornahawk 27 Jul 2009 02:00

Just to be clear…

$ed \equiv 1 \pmod m$ is what's equivalent to saying $ed \mod m= 1$ The correct symbols matter. ;)

"the modded values are not. shouldnt e*d mod m(or n) = 1? yet the stuff on wikipedia is giving large numbers that are no where close to 1"

What example is failing on you? I'll try to reproduce it on Mathematica.

thornahawk

Last edited on 27 Jul 2009 02:02 by thornahawk Show more

Re: generating the exponents in the first place

calccrypto 27 Jul 2009 02:01

wait! no! i got it! it was my mistake. i modded N, as in P*Q rather than the totient, (p-1)(q-1)

sorry!

---

Visit Calccrypto for info on crypto
KC2ZOF

Re: generating the exponents in the first place

thornahawk 27 Jul 2009 02:04

Don't feel too bad, it's a pretty common mistake that those starting out in computational number theory do. ;)

thornahawk

Re: generating the exponents in the first place

calccrypto 27 Jul 2009 02:36

thanks!

download!!!!!!!!!!!!!!!!!!

Python 2.6.2
My site

---

Visit Calccrypto for info on crypto
KC2ZOF

Re: generating the exponents in the first place

jnesselr 27 Jul 2009 02:45

Why not use lists? It would have a base of 256, and b 16 digits long. I think it's possible.

Re: generating the exponents in the first place

calccrypto 27 Jul 2009 03:36

i didnt bother with transforming to binary too many times, i think

---

Visit Calccrypto for info on crypto
KC2ZOF

Re: generating the exponents in the first place

calccrypto 27 Jul 2009 20:57

hm… i swear that the program was working yesterday. today, i ran it again, without changing anything, and its not working. any ideas?

i got it down to the MillerRabin function, but there cant be that many false positives can there??

---

Visit Calccrypto for info on crypto
KC2ZOF

Last edited on 27 Jul 2009 21:11 by calccrypto Show more

Re: generating the exponents in the first place

thornahawk 28 Jul 2009 01:30

"The sequence of smallest odd numbers passing a multiple Rabin-Miller test using the first k primes for k=1, 2, … is given by 2047, 1373653, 25326001, 3215031751, 2152302898747, 3474749660383, 341550071728321, 341550071728321, … (Sloane's A014233; Jaeschke 1993). Therefore, multiple Rabin tests using the first 7 primes (using 8 gives no improvement) are valid for every number up to 3.4×10¹⁴."

(source)

thornahawk

Re: generating the exponents in the first place

calccrypto 28 Jul 2009 03:05

okay… but it cant be returning false positives every time i run it can it? or am i just lucky?

---

Visit Calccrypto for info on crypto
KC2ZOF

Re: generating the exponents in the first place

DarkerLine 28 Jul 2009 03:31

I suggest first making sure the rest of your code works by taking two known primes, and using them instead of the random-prime operation you're currently doing. Once you get that working, you know any problems you get come from not properly choosing the primes.

Re: generating the exponents in the first place

calccrypto 28 Jul 2009 03:46

im basically copying the x86 code, with euclid stuff from wikipedia.

def getd(a,b):
# this is from wikipedia :
# http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
# the "Formal_description_of_the_algorithm" part
    x = 0    
    lastx = 1
    y = 1    
    lasty = 0
    while b != 0:
        quotient = a / b
        temp = b
        b = a % b
        a = temp
 
        temp = x
        x = lastx-quotient*x
        lastx = temp
 
        temp = y
        y = lasty-quotient*y
        lasty = temp
    return a                    # hopefully this is the correct value to return

def makekeys(size):
    bits = size/2
    p = 0; q = 0
    while p == q:
        a = random.randint(int(size**.5),size)
        x = 0
        while x<a:
            p = random.randint(2**(bits),2**(bits+1))    # Generate some random values    
            q = random.randint(2**(bits),2**(bits+1))    # for a random amount of times
            x = x+1
        while MillerRabin(p) == False:                    
            p = p + 1                            
            if len(bin(p))>bits:
                p = p % (2**(bits+1))                # While the number is not prime
        while MillerRabin(q) == False:                # add 1 to the value and mod if it 
            q = q + 1                                # gets too big (should i keep the mod?)
            if len(bin(q))>bits:
                q = q % (2**(bits+1))
    n = p * q    
    tot = (p-1) * (q-1)
    e = tot
    while gcd(tot,e) != 1:                            # find some value of e that is
        e = random.randint(3,tot-1)                  # coprime to the totient
 
    d = getd(tot,e)                                # find the inverse of the totient and e
                                                # which is supposed to comes first?
 
    while d<0:                                    # does this even belong here?
        d = d + n
    return e,d,n

---

Visit Calccrypto for info on crypto
KC2ZOF

Last edited on 28 Jul 2009 03:47 by calccrypto Show more

Re: generating the exponents in the first place

DarkerLine 28 Jul 2009 03:54

So replace the while p==q loop with, say, 100003 and 101963. Not nearly the bit length we're looking for, of course, but if the algorithm works for these, it probably works in general.

Re: generating the exponents in the first place

calccrypto 28 Jul 2009 15:15

wouldnt that possibly allow for repeats?

and for the euclid algorithm, which value is A and which is B? is A the value to mod by, or E? i might have put them in the wrong order

---

Visit Calccrypto for info on crypto
KC2ZOF

Re: generating the exponents in the first place

DarkerLine 28 Jul 2009 15:57

Oh, for the extended GCD, you returned the value of the GCD. But if you're calling it with getd(tot,e) as you're doing there, you'll want to return lasty instead. If you switched the order to getd(e, tot) you'd want to return lastx.

The order doesn't really matter, as long as you're consistent in this respect. But if A<B initially then you're doing one extra step to switch A and B. So the order you have right now, getd(tot,e), is the better option.

Edit: My previous suggestion does allow for repeats, and I'm not suggesting you use it in the final version. I'm suggesting you use it to test the rest of the code.

Last edited on 28 Jul 2009 16:06 by DarkerLine Show more

Re: generating the exponents in the first place

calccrypto 28 Jul 2009 21:31

ah. okay

thanks

---

Visit Calccrypto for info on crypto
KC2ZOF

Re: generating the exponents in the first place

calccrypto 29 Jul 2009 01:53

i dont get it. for some reason, the computer isnt reading the while loops. when i run this, with a "print", it keeps on displaying "2 2"

    p = 2
    q = 2
    while p == q:    
        while MillerRabin(p) == False:
            p = p + 1
#            % (2**(bits+1))
        while MillerRabin(q) == False:
            q = q + 1
#            % (2**(bits+1))

---

Visit Calccrypto for info on crypto
KC2ZOF

Last edited on 29 Jul 2009 04:37 by calccrypto Show more

Re: generating the exponents in the first place

DarkerLine 29 Jul 2009 15:07

Well, what do you expect to happen?

It starts of with p=q=2. Then as long as p==q, it checks if 2 is prime, which it is; it checks if 2 is prime again, and it still is; it continues looping without changing p or q.

Re: generating the exponents in the first place

calccrypto 29 Jul 2009 15:46

wow. im so stupid.

however, when i added the "change p,q into some random numbers" lines, it still skips the loops

also,

p = random.randint(2**(bits),2**(bits+1))
q = random.randint(2**(bits),2**(bits+1))
print MillerRabin(p),MillerRabin(q)
print p,q

i got :

False True
24758929329144963960 25958310095959522459

then i tested the second number, and it was false.

---

Visit Calccrypto for info on crypto
KC2ZOF

Last edited on 29 Jul 2009 16:31 by calccrypto Show more