Ask for algorithms for find large primes!

[tuyide]

Please help me!
How can I find a prime with 150 digits?
Are there any algorithms?

[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.

[tuyide]

But how can I proof this ?
Is ther any reference that I can refer to?

[gvcormac]

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.

[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).

[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.