Algorithm for quickly constructing the table of
reciprocals mod p, for a small odd positive prime, p.

Step 1: Generate a table of squares mod p.

Step 2: From the table of squares, generate the sqrt table.

Step 3: From the table of square roots, generate the reciprocal

table.




def ModRecipTable(p,SqrtTable):
mhalf = (p-1)/2
dex = 0
RecipTable = range(p)
last = p-1
dex = -1
while dex < last:
#{
dex = dex + 1
RecipTable[dex] = -1
#}
dex = -1
while dex < last:
#{
dex = dex + 1
if SqrtTable[dex - 1] != -1 :
#{
if SqrtTable[dex] != -1:
#{
#### Found two consecutive squares mod p.
s = SqrtTable[dex-1]
t = SqrtTable[dex]
x = (t - s)%p
y = (t + s)%p
RecipTable[x] = y
RecipTable[y] = x
RecipTable[p-x] = p-y
RecipTable[p-y] = p-x
#}
#}
#}
return RecipTable



def ModSqrtTable(p,SqTable):
last = p-1
SqrtTable = range(p)
### Fill the sqrt table with the "Does not have a square

root" flags.
dex = -1
while dex < last:
#{
dex = dex + 1
SqrtTable[dex] = -1
#}
mhalf = (p-1)/2
dex = -1
while dex < mhalf:
#{
dex = dex + 1
SqrtTable[SqTable[dex]] = dex
#}
return SqrtTable




def ModSqTable(p):
mhalf = (p-1)/2
dex = -1
SqTable = []
while dex < mhalf:
#{
dex = dex + 1
SqTable.append((dex\*dex)%p)
#}
return SqTable