Skip to content

Instantly share code, notes, and snippets.

@k06a
Last active February 7, 2022 15:07
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save k06a/b990b7c7dda766d4f661e653d6804a53 to your computer and use it in GitHub Desktop.
Save k06a/b990b7c7dda766d4f661e653d6804a53 to your computer and use it in GitHub Desktop.
Modular inverse with binary shifts and uint256
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.11;
contract ModInv {
uint256 public constant n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F;
function inverseDiv(uint256 a) public pure returns(uint256) {
return inverseDiv(a, n);
}
// https://github.com/jbaylina/ecsol/blob/c2256afad126b7500e6f879a9369b100e47d435d/ec.sol#L51-L67
function inverseDiv(uint256 a, uint256 m) public pure returns(uint256 t) {
uint256 newT = 1;
uint256 r = m;
uint256 newR = a;
uint256 q;
while (newR != 0) {
q = r / newR;
(t, newT) = (newT, addmod(t , (m - mulmod(q, newT, m)) , m));
(r, newR) = (newR, r - q * newR);
}
}
function inverseShift(uint256 a) public pure returns(uint256) {
return inverseShift(a, n);
}
// https://www.researchgate.net/publication/304417579_Modular_Inverse_Algorithms_Without_Multiplications_for_Cryptographic_Applications
function inverseShift(uint256 a, uint256 m) public pure returns(uint256) {
unchecked {
uint256 u;
uint256 v;
uint256 r;
uint256 s;
if (a < m) { u = m; v = a; r = 0; s = 1; }
else { v = m; u = a; s = 0; r = 1; }
uint256 llu = ll(u, true);
uint256 llv = ll(v, true);
uint256 flip = 0;
for (uint i = 0; v + 1 > 2; i++) { // not 0 +/-1
uint256 f = llu - llv;
if ((1 - (u >> 255)) | (i < 1 + flip ? 1 : 0) == (1 - (v >> 255)) | (i < 1 + (1-flip) ? 1 : 0)) {
u = u - (v << f);
r = r - (s << f);
}
else {
u = u + (v << f);
r = r + (s << f);
}
llu = ll(u);
if (llu < llv) {
flip = 1;
(u,v,r,s,llu,llv) = (v,u,s,r,llv,llu);
}
}
if (v == 0) { return 0; }
if (v >> 255 == 1) { s = 0-s; }
if (s >> 255 == 0 && s > m) { return s - m; }
if (s >> 255 == 1) { return s + m; }
return s;
}
}
function ll(uint256 a) public pure returns(uint256 ret) {
return ll(a, false);
}
function ll(uint256 a, bool forcePositive) public pure returns(uint256 ret) {
if (!forcePositive && ((a >> 255) == 1)) {
unchecked {
a = 0-a;
}
}
ret = (a > 0) ? 1 : 0;
for (uint k = 128; k > 0; k >>= 1) {
uint256 b = a >> k;
if (b > 0) {
ret += k;
a = b;
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment