Browse Groups

• ## Re: [PrimeNumbers] Digest Number 2756

(1)
• NextPrevious
• ... Hello Richard. Actually, it is very much faster than the extended Euclidian. This is because it does the whole reciprocal table at once, instead of one
Message 1 of 1 , Jul 23, 2009
View Source
>
> Messages in this topic (3)
> ________________________________________________________________________
> 2b. Re: Fast algorithm to construct table of reciprocals mod p for small
> Date: Wed Jul 22, 2009 8:44 pm ((PDT))
>
> --- In primenumbers@yahoogroups.com, Kermit Rose <kermit@...> wrote:
>
>
>> Algorithm for quickly constructing the table of
>> reciprocals mod p, for a small odd positive prime, p.
>>
>
> Your algorithm is faster than the extended euclidian? Don't think so!
>
> Richard Heylen
>

Hello Richard.

Actually, it is very much faster than the extended Euclidian.

This is because it does the whole reciprocal table at once, instead of
one inverse at a time.

I feel, but have not proven, that it will also be faster than Phil's
suggestion of powers of comparing
powers of 1/2 to powers of 2 mod p, then
powers of other integers for which the mod reciprocal had been
previously calculated.

Of course Phil's comment is well taken,
that the memory requirements of this method make it impractical
for primes large enough that
any difference in efficiency would be noticed.

My algorithm is of theoretical interest, not computational practicality
interest.

To make the method more clear, I shall illustrate it by calculating the
table of inverses mod 13.

Calculate the squares mod 13.

1**2 = 1 mod 13
2**2 = 4 mod 13
3**2 = 9 mod 13
4**2 = 3 mod 13
5**2 = 12 mod 13
6**2 = 10 mod 13

From this Squares table calculate the sqrt table as follows.

First fill the sqrt table with flags -1

sqrt(0) = -1
sqrt(1) = -1
sqrt(2) = -1
sqrt(3) = -1
sqrt(4) = -1
sqrt(5) = -1
sqrt(6) = -1
sqrt(7) = -1
sqrt(8) = -1
sqrt(9) = -1
sqrt(10) = -1
sqrt(11) = -1
sqrt(12) = -1

Now from the squares table,

0**2 = 0 mod 13
1**2 = 1 mod 13
2**2 = 4 mod 13
3**2 = 9 mod 13
4**2 = 3 mod 13
5**2 = 12 mod 13
6**2 = 10 mod 13

Invert it to get,

sqrt(0) = 0
sqrt(1) = 1
sqrt(4) = 2
sqrt(9) = 3
sqrt(3) = 4
sqrt(12) = 5
sqrt(10) = 6

sqrt(0) = 0
sqrt(1) = 1
sqrt(2) = -1
sqrt(3) = 4
sqrt(4) = 2
sqrt(5) = -1
sqrt(6) = -1
sqrt(7) = -1
sqrt(8) = -1
sqrt(9) = 3
sqrt(10) = 6
sqrt(11) = -1
sqrt(12) = 5

Now use the sqrt table in one pass to find all the reciprocals.

First reserve the space for the reciprocals.

recip(1) = -1
recip(2) = -1
recip(3) = -1
recip(4) = -1
recip(5) = -1
recip(6) = -1
recip(7) = -1
recip(8) = -1
recip(9) = -1
recip(10) = -1
recip(11) = -1
recip(12) = -1

In the sqrt table, search for the (13-1)/4 consecutive squares mod 13.

sqrt(0) = 0
sqrt(1) = 1
sqrt(2) = -1
sqrt(3) = 4
sqrt(4) = 2
sqrt(5) = -1
sqrt(6) = -1
sqrt(7) = -1
sqrt(8) = -1
sqrt(9) = 3
sqrt(10) = 6
sqrt(11) = -1
sqrt(12) = 5

The first consecutive squares are

1 = 0 - 12 = 0**2 - 5**2 = (0 - 5) * (0 + 5)

Thus 13 - 5 = 8 and 5 are multiplicative inverses.

recip(5) = 8
recip(8) = 5

Next pair of consecutive squares is:

0**2 = 0 and 1**2 = 1
thus 1 = 1 - 0 = 1**2 - 0**2 = (1 - 0) * (1 + 0)

1 and 1 are inverses.

This warrants our setting
recip(1) = 1 and
recip(12) = 12

The next consecutive squares are 4**2 = 3 and 2**2 = 4.

Thus 1 = 4 - 3 = 2**2 - 4**2 = (2 - 4) * (2 + 4)

That is, (2 - 4) and (2 + 4) are multiplicative inverses mod 13.

11 * 6 = 1 mod 13
This yields immediately
recip(11) = 6
recip(6) = 11
recip(13-11) = 13 - 6
recip(13-6) = 13 - 11

The next consecutive squares are

1 = 10 - 9 = 6**2 - 3**2 = (6-3) * (6 + 3)

6 - 3 = 3 and 6 + 3 = 9 are multiplicative inverses mod 13.

So now the reciprocal table is complete.

recip(1) = 1
recip(2) = 7
recip(3) = 9
recip(4) = 10
recip(5) = 8
recip(6) = 11
recip(7) = 2
recip(8) = 5
recip(9) = 3
recip(10) = 4
recip(11) = 6
recip(12) = 12

Kermit Rose
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.