Just wondering if there is a bug with primality testing

[anfractuosity]

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;
}

[kunerd]

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.