View Single Post
Old 2015-09-27, 15:13   #9
science_man_88's Avatar
"Forget I exist"
Jul 2009

26×131 Posts

Originally Posted by R.D. Silverman View Post
It is possible that with moderate effort one can show that a
billion digit number isn't prime, but such a demonstration requires luck.
like for a number of form k*b^n+1 you can prove that if gcd((k-y)*b^n,y*b^n+1)!=1 that it's composite but this could require as many as k separate tests.
science_man_88 is offline   Reply With Quote