View Single Post
Old 2011-05-25, 07:32   #33
JohnFullspeed
 
May 2011
France

7·23 Posts
Default 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
JohnFullspeed is offline   Reply With Quote