Refactor SSWU to use div_sqrt per Daira's suggestion.

[chris-wood]

This does not include an efficient, constant time implementation of div_sqrt (yet!), so I'm starting this as a draft for us to work through that. It's not clear to me how we can adapt Tonelli-Shanks here. Help is appreciated! =)

cc @kwantam, @armfazh

[kwantam]

I will have time either later this week or next week to (finally!) look at this. Sorry for the delay!

[chris-wood]

@kwantam I finally got around to updating this PR. I promoted the generalized SSWU variant from @daira to the appendix, removed curve-specific optimizations, and updated the reference code. This could really use a review, so please let me know if there's anything else I could do to help!

[mratsim]

Note the constant-time Tonelli Shanks that returns invsqrt at https://github.com/miracl/core/issues/24

Sage implementation: https://github.com/mratsim/constantine/blob/499f9605/sage/square_root_bls12_377.sage#L222-L248

[kwantam]

This could really use a review, so please let me know if there's anything else I could do to help!

Sorry for the long long delay on this. I'm buried in dissertation work for the next couple weeks, but after that things will be better. (Feels like I've said that before! but this is top of my priority list post-dissertation...)

[chris-wood]

@mratsim thanks! I'll take a look.

[kwantam]

I'm getting back up to speed on this and reviewing today (and probably tomorrow)! Phew... sorry for the long delay.

[kwantam]

@chris-wood would it make sense for us to add field-specific implementations of sqrt_ratio? That's implicitly what we had before, and given that in most cases folks will be working with primes congruent to 3 mod 4 or to 5 mod 8, it seems reasonable to include at least those two optimizations (to me, 9 mod 16 probably also makes sense).

[chris-wood]

Maybe? What would be the concrete improvement? Can we do that in a separate PR if necessary?

[kwantam]

The field-specific implementations are a lot simpler than the generic one.

[kwantam]

We could do in a separate PR, or I could make a PR against this PR. What do you prefer?

[chris-wood]

Let's do a separate PR. Is this one good to go?

[daira]

I can do a more thorough review of this tomorrow. (If I don't get round to it, don't block on me.)

[chris-wood]

Thanks @daira! @kwantam, please let me know if changes are needed or not. I'll prioritize adding them.

[chris-wood]

@kwantam regarding mechanical changes -- the pseudocode here is copied directly from the reference implementation underneath. Were you thinking of a different sort of mechanical conversion? (I don't recall us doing anything else here, but it has been a while...)

[chris-wood]

@kwantam pseudocode and tests updated. Please have another look!

[chris-wood]

@kwantam resolved -- awaiting your green light.

[kwantam]

@chris-wood I pushed a tiny change in test.sage that removes an extraneous call to an undefined straight_line2 method. Re-running tests now.

[kwantam]

sqrt tests were too slow because they had to recompute primitive_element each time. I memoized that computation and reduced the bit width of random moduli for the test. Re-launching now.

Please double check my last two commits! I will post again when tests converge.

[chris-wood]

@kwantam last two commits LGTM!

[chris-wood]

@kwantam feel free to put up the field-specific sqrt_ratio PRs now. Let's keep the momentum going!

[daira]

I know this is already merged, but I reviewed it again anyway.

[chris-wood]

Thanks @daira :) I'll review the comments above and try to address them in subsequent PRs, assuming @kwantam doesn't beat me to it.

[kwantam]

Thanks @daira :) I'll review the comments above and try to address them in subsequent PRs, assuming @kwantam doesn't beat me to it.

@chris-wood I will plan to roll these changes into my PR.