Thread: Fast isPrime() for n < 2^32 View Single Post
 2011-05-25, 07:32 #33 JohnFullspeed   May 2011 France 7·23 Posts a:=a*a mod N 10000 bits if you want.... In fact you can use this mrethod for othezr problems as divisioins.. The method is: Let A and B be big positive integerss Let ? an sllower opoeraareationn A ? B = C you work on the binary representation each bit of A If te bit is 0 you make a specific code if the bit is 1 you make and other code you pass to, the Bit after unil A have bit Code: function E_M(m, K, N: int64): int64; var b, a: int64; begin b := 1; a := m; if odd(k) then b := A; k := k shr 1; <= first bit of tha operande repeat A := (A * A) mod N; <= in all casae Bit=0 or Bit=1 if odd(k) then <= the bit is 1 b := (A * b) mod N; k := k shr 1; <+ nexT bit until k = 0; <= no new bit (end) result := b; end; if you remove the mod you have a speed exopanciation Is't easy to do a faster div.... A := (A * A); <= in all casae Bit=0 or Bit=1 if odd(k) then <= the bit is 1 b := (A * b); k := k shr 1; <+ nexT bit until k = 0; <= no new bit (end) You understood that A can have 1000 bios you make 'only' 1000+5000 divmod John