Page 1 of 1
Ask for algorithms for find large primes!
Posted: Fri Dec 12, 2003 10:09 am
by tuyide
Please help me!
How can I find a prime with 150 digits?
Are there any algorithms?
Posted: Sat Dec 13, 2003 5:21 am
by gvcormac
Just do a linear search using the fermat test.
If a^(p-1) == 1 (mod p) for some a you can bet everything you own that p is prime.
If you want 'proof' you have to work a little harder.
Posted: Sun Dec 14, 2003 8:53 am
by tuyide
But how can I proof this ?
Is ther any reference that I can refer to?
Posted: Sun Dec 14, 2003 1:57 pm
by gvcormac
tuyide wrote:But how can I proof this ?
Is ther any reference that I can refer to?
Search the web for "fermat primality test."
There's a whole body of literature on primality testing,
both probabilistic and deterministic. But the bottom
line is that if you pick some big number and it passes
the fermat test, you can discount the probability that
it is not prime.
Posted: Tue Dec 16, 2003 2:35 pm
by tuyide
thnx!gvcormac.
Furthermore,can anybody tell me how can I compute whether a^(p-1) == 1 (mod p) ?
You know,it is very hard for me to calculate for the prime is too large(with 100 digits).
Posted: Wed Dec 17, 2003 12:35 am
by gvcormac
You want to compute a^n.
The binary representation of n is b0 + 2b1 + 4b2 + ... (2^m)bm
So a^n is a^b0 * a^2b1 * ... a^(2^m)bm
So compute a^(2^m) for all m and multiply together the ones for which bm == 1.
Do all this arithmetic modulo p.
You can compute the a^(2^m) by squaring a m times. Then up to m
more multiplications for a total of 2m.
There's a slightly sneaker way that avoids
explicitly computing the a^m's, and takes only m multiplicationis.
Of course you still have to be able to multiply and divide big integers.