Re: challenge Message #13 Posted by hugh steers on 16 Apr 2010, 10:01 p.m., in response to message #12 by Bart (UK)
I used my own of course :-)
I'm using Reckon on the 9860g. I haven't developed a CAS for it yet (although i do have some work in this direction). However, it does support big ints and has some factoring code.
you are correct, that the "prime" test method uses a probabilistic algorithm. to reject composites i use a strong pseudoprime test up to the Riemann limit = min(floor(2ln(n)^2), n-1) or 50 trials whichever is the smallest. 50 is an arbitrary number for confidence. hand waving theory says this gets 2^-50:1 of being wrong. i'd like to do more trials, but calculators are slow.
however, you can just punt the number to the "fac" method, which attempts factorisation (it's also short to type than "prime"). the fac method uses a series of approaches including prime testing.
firstly, "fac" attempts trial division. for this i use my "division without division" method to find any factors up to 2^20. here's an article on this method i wrote a while back
http://www.voidware.com/hpcc/smallfactor.pdf. Actually this approach is suitable for factoring any number up to 12 digits in length in under 10 seconds, but not for larger numbers.
if the above fails to find a factor, the strong pseudo prime test is applied, either up to the Riemann limit or 50. if it thinks the number is prime, then the process stops. most often the method finds a "witness" for a composite, in which case prime testing quits and we move on.
if we get past the trial division and prime test, then we have a composite with a factor > 2^20. now we're in trouble! my old code used to use a bunch of methods including pollard rho, Fermat and shanks' square free method. since then ive implemented Lenstra's elliptic curve method (ECM) and, without a doubt, this method dominates all others. the other attempts are no longer attempted and "fac" moves right away to the ECM.
the ECM is the third best known factoring method. unfortunately the other two, the quadratic sieve, and (general) number field sieve cannot be implemented on calculators because they require a large amount of memory. the ECM requires hardly any and is a very beautiful method which has running time proportional to the smallest factor - a highly desirable property!
the theory and efficient implementation are covered in Crandall & Pomerance, "prime numbers", chapter 7, 2nd edition. the authors develop a number of important optimisations to the method. i have followed these in my implementation but i have not gone as far as the Montgomery arithmetic (it's totally weird!)
if you want to try this out,
checkout http://www.voidware.com/reckon/ for the casio
or for the PC exe get,
http://www.voidware.com/reckon/reckon.exe
try these
a=1741^9-1
a=a/9+151
prime(a)
or fac(a)
also try,
a=2^73-1
a=a/439
fac(a)
or even
fac(2^103-1)
Bart, thanks for the comments. FTI, i just uploaded a new reckon casio binary 1.15 no actual change except that i just noticed it was suddently taking a _lot_ longer to factor numbers. turned out it was the escape key test i put in recently (you can press "EXIT" whilst factoring to abort). this _really_ slowed it down, so i moved this test out of an inner loop and its fine now.
|