Sage script for dlog precomp constants calculation

[advaita-saha]

The PR #354 adds the pre-comp optimisation for sqrt, which has the constants prepared only for

• Banderwagon Curve
• Bandersnatch Curve

A sage script is supposed to be added for the calculation of the these constants for other curves. The algorithm for the calculation of the constants can be found here
https://github.com/crate-crypto/go-ipa/blob/408dbffb2041271c95979a3fb79d98b268bf2880/bandersnatch/fp/sqrt.go#L45-L89

A corresponding sage script is supposed to be created and added inside the sage folder

[rupam-04]

@mratsim As far as I know, sage only supports Weierstrass curves and doesn't support Twisted Edwards curves like Banderwagon and Bandersnatch. So is there any way around this?

[mratsim]

@mratsim As far as I know, sage only supports Weierstrass curves and doesn't support Twisted Edwards curves like Banderwagon and Bandersnatch. So is there any way around this?

We're working at the field level so we only need

Fp = GF('0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001')

[mratsim]

Pasting my comment on modularization #369 (comment)

One thing though that I think is important is this:

* https://github.com/pornin/modsqrt/blob/0a9c69a0ce8b4a031e7f4a728a3bd93870088ecf/modsqrt.sage#L133-L138

* https://github.com/pornin/modsqrt/blob/0a9c69a0ce8b4a031e7f4a728a3bd93870088ecf/modsqrt.sage#L232-L236

#  - When lb is small enough, this is a matter of recognizing the value z
#    among the known 2^lb-th roots of 1, with a "reverse lookup". This can
#    be done by using only a small number of bits from the value (see the
#    minhc() function in the code below, to find a minimal-sized bit
#    pattern that is enough to distinguish all roots). We can thus stop
#    the recursion before reaching lb == 1.

and the function minhc: https://github.com/pornin/modsqrt/blob/0a9c69a0ce8b4a031e7f4a728a3bd93870088ecf/modsqrt.sage#L535-L559

Ergo, we are using a LUT of window 8 (see also https://hackmd.io/@jsign/bandersnatch-optimized-sqrt-notes#Detailed-comparison):

constantine/constantine/math/constants/banderwagon_sqrt.nim

Lines 167 to 172 in d7871d7

	const
	Banderwagon_SqrtDlog_TotalBits* = Banderwagon_TonelliShanks_twoAdicity
	Banderwagon_SqrtDlog_BlockSize* = 8
	Banderwagon_SqrtDlog_Blocks* = 4 #Banderwagon_TonelliShanks_sqrtParam_TotalBits / Banderwagon_TonelliShanks_sqrtParam_BlockSize
	Banderwagon_SqrtDlog_FirstBlockUnusedBits* = Banderwagon_SqrtDlog_Blocks*Banderwagon_SqrtDlog_BlockSize - Banderwagon_SqrtDlog_TotalBits
	Banderwagon_SqrtDlog_BitMask* = (1 shl Banderwagon_SqrtDlog_BlockSize) - 1

but we're lucky because 8-bit patterns can uniquely identify the root-of-unity we need.