MCPcopy Create free account
hub / github.com/TheAlgorithms/Rust / tonelli_shanks

Function tonelli_shanks

src/math/quadratic_residue.rs:141–192  ·  view source on GitHub ↗

Returns one of the two possible solutions of _x² = a mod p_, if any. The other solution is _-x mod p_. If there is no solution, returns `None`. Reference: H. Cohen, _A course in computational algebraic number theory_, Algorithm 1.4.3 ## Implementation details To avoid multiplication overflows, internally the algorithm uses the `128`-bit arithmetic. Also see [`cipolla`].

(a: i64, odd_prime: u64)

Source from the content-addressed store, hash-verified

source not stored for this graph (policy: none)

Callers 1

tonelli_shanks_residuesFunction · 0.85

Calls 2

fast_powerFunction · 0.85
legendre_symbolFunction · 0.85

Tested by

no test coverage detected