BigInt icon indicating copy to clipboard operation
BigInt copied to clipboard

Is probable prime

Open KingAkeem opened this issue 7 years ago • 2 comments

#5 I've added the is_probable_prime method using Rabin Miller primality testing. I started with Little Fermat's Theorem and built from that. I also had to add a utility function in order to calculate much needed values. I've added a test to cover the base cases but I've ran a number of test using extremely large primes and a variety random primes using random generators. The test is fast and very accurate based on the certainty passed to it.

KingAkeem avatar May 16 '18 01:05 KingAkeem

Some cases fail:

-------------------------------------------------------------------------------
is_probable_prime() for big integers true
-------------------------------------------------------------------------------
BigInt/test/functions/math.cpp:397
...............................................................................

BigInt/test/functions/math.cpp:401: FAILED:
  REQUIRE( num.is_probable_prime(25) == 1 )
with expansion:
  false == 1

-------------------------------------------------------------------------------
is_probable_prime() for big integers false
-------------------------------------------------------------------------------
BigInt/test/functions/math.cpp:412
...............................................................................

BigInt/test/functions/math.cpp:414: FAILED:
  REQUIRE( num.is_probable_prime(25) == 0 )
with expansion:
  true == 0

===============================================================================
test cases:   19 |   17 passed | 2 failed
assertions: 1411 | 1409 passed | 2 failed

faheel avatar Oct 29 '18 11:10 faheel

Going to take a lot at this again soon

KingAkeem avatar Jan 18 '23 15:01 KingAkeem