Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Fri Aug 21 1998 - 17:16:58 ADT
Thomas Womack (thomas.womack@merton.oxford.ac.uk)
Sun, 26 Apr 1998 13:16:11 +0100
>Zhang Ya-ming <yamn@public.bjnet.edu.cn> writes:
>
>> But all these method can only declare a pesudo-prime, so you
would
>> get a true prime number in probability.
>
>And that is okay. There is no way to do test for a "real" prime number
>with a computer - the probability that cosmic radition switches one bit
>in you memory is MUCH higher than the failure of several pseudo-prime
tests.
That's just not true; consider the Jacobi-sum primality-proving techniques,
or ECPP, both of which are guaranteed, if executed correctly, to declare
only primes prime, and at least one of which produces a certificate of
primality, which can be checked in time less than the original test.
Or consider the really straightforward prime-certification method
(impractical for primes of any interesting size) of giving a factorisation
of p-1 and demonstrating the existence of a primitive root of p by showing k
: k^{p-1} = 1 and k^{p-1/q} \not = 1 for q a factor of p-1.
'2^16+1 is prime, because 65536 = 2^16 and 3^32768 = -1 mod 65537'
Tom
The following archive was created by hippie-mail 7.98617-22 on Fri Aug 21 1998 - 17:16:58 ADT