Re: Q:About primes?


"Dan" <30pack@xxxxxxxxxxxxx> wrote in message
news:13663801.1136497130495.JavaMail.jakarta@xxxxxxxxxxxxxxxxxxxxxxxxx
> Q:About primes?
>
> Why does a certain large prime require much more
> processing time to verify its primality than one that
> is more than 60 times its size?
>
> e.g.
>
> This prime below with 749 digits required 17+ hours to
> establish its primality.
>
> 30535097901345064310236174839489700080459663520096
> 69602323498345043501772521614789116618159734458191
> 33012276115769665116991385003007412849595725955497
> 82539025065316343685145506155812832930826308169991
> 03235521001534695731579798918213609701985238868299
> 05496367134467697182318980972065541838326121951538
> 51781656086684834199171972635458068998756131746296
> 31420187415749557187675872346102211430205807025283
> 26705059999206625008430333192533577908997722753658
> 00363494431851465001513590565074718403193054203954
> 12026385658659107627667163043534168346074818615904
> 03907488402966740762510012534574398079748765760746
> 92538684507407889491956489657862373272667461155274
> 58446365135106689722576148786264906866555969699021
> 2902628454402671432601097708301629332576840702301
>
> Whereas this prime below with 751 digits that is more
> than 60 times the size of the above prime took a little
> more than 5 hours to establish its primality.
>
> 21050265664569505769747657916173104050801827994035
> 28900317501493517070407298733921181990193407231801
> 43779408314930824549947110712317894480745373003159
> 21609632251704831259629428482666756056164418464321
> 45924606837701476025109370522412427317600804201258
> 57752617867042568131395890575081564774449072424545
> 61562203237127127715927715805695165379004622744086
> 33824748961582141083837458534816036730734320316375
> 10015304390077652342973808023948567899720274885017
> 91725615628604900118526886951303916264715442921635
> 01827664696110096809557007351405735419350432680968
> 09849034558962642757629291379218668705620426295819
> 31347136109687471629580989255229645075893447269762
> 76271163934758185867446989768887541305780135020808
> 082967563934122807704444794896789338846027416989917
>
> Both verified as primes under the APRT-CLE process.
>
> Dan
Consider P an odd number, hence a prime candidate.
A typical "Prime Testing Algorithm" is if ..base^(P-1) mod P = 1
is true using 4 different bases (say 2,3,5,7) then P is "probably prime"
The trick to handling such monsters is to repeatedly divide (P-1) by
the number 2 until the number 1 is all that is left. Using decimal
arithmetic
it takes roughly 4 times 751 =3004 (your second candidate) steps to do
this.
And each of these 3004 steps will be associated with a modulus of 2.
ie either a 1 or 0. If you are lucky your "other" computations will deliver
a "1"
ie "P probably prime" early. and if the higher steps are associated with
all zeros on the division ladder then computation speed is dramatically
increased. You only have to keep squaring the number "1" instead of mod of
some monster lengthed digit. This saving is repeated for all of the bases
that you run your test with. From this it can be seen that number of
digits alone do not define computation time. You need an understanding
of modular arithmetic to fully grasp what is happening.
Some prime testing algorithms will run yet more tests to guarentee
that the candidate is in fact prime instead of only probably prime.
HTH Mick.


.

Relevant Pages

  • Re: Q:About primes?
    ... >> establish its primality. ... >> Both verified as primes under the APRT-CLE process. ... p749 to verify more easily. ...
    (sci.math)
  • Re: Q:About primes?
    ... >>> processing time to verify its primality than one that ... Your first number is 751 digits. ...
    (sci.math)
  • Re: Q:About primes?
    ... >> processing time to verify its primality than one that ... >> establish its primality. ... Prev by Date: ...
    (sci.math)
  • Re: smallest prime number greater than n
    ... prime or not...up to 18 digits. ... primality of an 18-digit number via trial-division. ... You don't want to prove primality via trial division ... In other words there are more advanced methods but some ...
    (sci.math)
  • Re: Q:About primes?
    ... > processing time to verify its primality than one that ... > establish its primality. ... It depends on how p-1 and p+1 factor. ...
    (sci.math)
Loading