partial_d: sage solve_mod efficiency

[MartinDlry]

RsaCtfTool/sage/partial_d.sage

Line 28 in c43d654

results = solve_mod([e * dLow * X - k * X * (n - X + 1) + k * n == X], 2 ^ lowerBitsNum)

The sage solve_mod function seem sub-optimal for this use case.

I compared it with this python implementation of Hensel Lemma: https://github.com/gmossessian/Hensel/blob/de6ddc91718e28950dd8cff9f4a2a4eab5cda383/Hensel.py with the following code :

import random
import time
import sys

sys.setrecursionlimit(10000)

tests_per_size = 100
max_size = 2048
size = 64
while size <= max_size:

    print(f"size={size}:")

    triplets = [[random.randint(2**(size-1), 2**size - 1) for _ in range(3)] for _ in range(tests_per_size)]

    hensel_equations = map(lambda t: Polynomial((t[0],t[1],t[2])), triplets)
  
    start = time.time()
    for eq in hensel_equations:
        hensel_results = Hensel(eq, 2, size)
    hensel_time = time.time() - start

    X = var('X')
    sage_equations = map(lambda t: t[0]*X^2 + t[1]*X + t[2] == 0, triplets)
    
    start = time.time()
    for eq in sage_equations:
        solve_mod_results = solve_mod(eq, 2**size)
    solve_mod_time = time.time() - start

    assert sorted(hensel_results) == sorted(map(lambda x: x[0], solve_mod_results))

    print(f'    average hensel time = {hensel_time/tests_per_size}s')
    print(f'    average solve_mod time = {solve_mod_time/tests_per_size}s')
    print(f"    ratio={solve_mod_time/hensel_time}")

    size *= 2

I obtained the following results :

size=64:
    average hensel time = 0.0003850793838500977s
    average solve_mod time = 0.49289143085479736s
    ratio=1279.9735626632985

size=128:
    average hensel time = 0.0008318185806274414s
    average solve_mod time = 1.3749861097335816s
    ratio=1652.9879732867093

size=256:
    average hensel time = 0.0017818999290466308s
    average solve_mod time = 2.639525330066681s
    ratio=1481.2982968571669

size=512:
    average hensel time = 0.004178078174591065s
    average solve_mod time = 5.779422121047974s
    ratio=1383.2728540589462

size=1024:
    average hensel time = 0.010017552375793458s
    average solve_mod time = 10.744901268482208s
    ratio=1072.6074459512013

size=2048:
    average hensel time = 0.02609231948852539s
    average solve_mod time = 17.815475981235505s
    ratio=682.7862118226096

I've no idea about the complexity of those two algorithms, however, for numbers with practical sizes, there is a 1000x speed factor.

[daedalus]

Hi,
Interesting idea, can you send a PR?

[MartinDlry]

Hello (sorry i forgot that part, i was too focused on the content of my message)

I could send a PR but i didn't how i should proceed. Do we just copy paste the code i linked ?

[daedalus]

No, you need to fork the repo git clone it, do a commit with your changes, test that it doesn't break anything, git push, and at last send a PR.

[MartinDlry]

Hum, yes, sorry maybe my message wasn't clear enough. I know how to do a PR. The code I used is from another repo, and as it isn't a library, I thought best i could do was copy and paste it into the project to use it. Now that i had time to understand what it does, i think i'll be able to refine it.

[daedalus]

Please avoid verbatim copying of someone else's code, try to implement by yourself the Hensel's lifting lemma.