There are many techniques through which we detect the prime numbers
so today we discuss these probabilistic method let's
first discuss fermat's prime test fermats primilarity
for the fermats little theorm there must be a and p
and such that they are coprimes then
so we to solve that
then the number is prime.
for solving this equation you get to know modular
exponential which is shown by example:-
now this technique is called modular exponential
in the fermats primilarity if you get the 1 after solving .
Then the number is prime else not
you can check and test the code here fermaths primilarity test
testing can be done at here see the
1 )upload with new input option click on it
2)inset the prime number enter submit
i have also implemented big integer multiplication similar
to modular exponential to multiply big numbers now you
think that we met the god of prime tester but it is not
there are numbers which act like prime but are not prime called carmichael number for example
test of 4903921 revels it is prime but it is not
here comes the concept of miller rabin
it says of a prime number would be two trivial
square roots 1 and -1(mod n).-1(mod n) = n-1(mod n)
more elegently described pseudocode described at
pseudocode of miller rabin test my job of implementation
here test the code with more inputs miller rabin test
i want to come up with more interesting algorithms till then NJOY
No comments:
Post a Comment