Just wondering if there is a bug with primality testing
Opened this issue · 1 comments
When I do the following using your miller_rabin algorithm
println!("{}",miller_rabin(&Int::from_str_radix("8822644427775620595775115476130893017686687877955563534429320360900846719257311242134794074876598682100945768516181513954573564989496411792485026178767949",10).unwrap(), 1024));
it returns false, indicating the number isn't a prime.
However according to a python implementation and wolfram alpha, that is classed as a prime.
It seems to be returning false due to:
if x != n_minus_one{
return false;
}
There are many possible reasons for the behaviour you describe. First, the current implementation is more or less a prove of concept and not really production ready. Another reason could be, that most implementations use a combinational approach of Fermat and/or Solovay-Strassen and Miller-Rabin test to check if a number is possible prime. You also have to notice, that all these Algorithms are probabilistic primality tests, which mean that results maybe differ from time to time.
At the moment I am working on the integration of the algorithms from bigint_extensions into ramp. Then I will look at this issue in more detail.