Created
November 27, 2025 06:02
-
-
Save MurageKibicho/4c2b7539faab0017738a5a90e800ff38 to your computer and use it in GitHub Desktop.
Folding Bit Tracker
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import random | |
| import math | |
| p = 2**256 - 2**32 - 977 | |
| def pseudo_mersenne_reduce(x, p): | |
| # Split into high and low 256-bit parts | |
| x_low = x & ((1 << 256) - 1) | |
| x_high = x >> 256 | |
| # First fold: add high * (2^32 + 977) | |
| x = x_low + x_high * (2**32 + 977) | |
| print(f'fold1: x: {math.log2(x)}, x_low:{math.log2(x_low)}, x_high:{math.log2(x_high)}') | |
| # Second fold: fold any bits above 256 again | |
| x_low = x & ((1 << 256) - 1) | |
| x_high = x >> 256 | |
| x = x_low + x_high * (2**32 + 977) | |
| print(f'fold2: x: {math.log2(x)}, x_low:{math.log2(x_low)}, x_high:{math.log2(x_high)}\n') | |
| # Third fold: in case still above 256 bits | |
| x_low = x & ((1 << 256) - 1) | |
| x_high = x >> 256 | |
| x = x_low + x_high * (2**32 + 977) | |
| # Final conditional subtraction | |
| if x >= p: | |
| x -= p | |
| return x | |
| # Test on many random pairs | |
| trials = 100 | |
| sub_counts = {0: 0, 1: 0} | |
| for _ in range(trials): | |
| a = random.getrandbits(256) | |
| b = random.getrandbits(256) | |
| product = a * b | |
| reduced = pseudo_mersenne_reduce(product,p) | |
| expected = product % p | |
| assert reduced == expected, "Mismatch!" | |
| print(f"After {trials} random 256-bit multiplications:") | |
| g = 0x4d47df04ac6c34a7b2d298cf24b1f428581a532c1f341aef39854f1a6fc160c9e0b42296a4d71cc29cec023ed105a686b6ca11c288bb8962253c82920491de8 | |
| t0 = g % p | |
| t1 = pseudo_mersenne_reduce(g,p) | |
| diff = p - t1 | |
| print(f'{t0}\n{t1:x}\n') | |
| print(f'{p:x}') |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment