1
$\begingroup$

Could someone please tell me where I can find the source code of the Coppersmith method univariate written in C with the GMP library?

to be fair I will explain how I will use it for factoring

reference https://www.academia.edu/48848013/Lepore_Factorization_nr_88

Let's take the example N=1763 of Factorization nr 88 Part I

$P=27*b+1$ ; $p=65-8*b$

$Q=25*a+11$ ; $q=67-8*a$

$p^2=(65-8*b)^2=64*b^2-1040*b+4225$

We find the integer delta $D$ of $x*p+p^2$

$(27*x-1040)^2-4*64*(4225+x)=D^2$

$x=1/729*(28208-sqrt(729*D^2+795691264))$

$795691264=1763*451328$

A partial factorization of $451328$ that is $8$ is the biggest problem with my approach

we replace $D$

$28208-729*x-27*sqrt[(27*x-1040)^2-4*64*(4225+x)]=8*(67-8*a)$

$->$

$64*a^2+55344*a+11964681=729*W$

$55344+729*x=64*y$ $->$ $x=16$

$11964681+729*x=64*y$ $->$ $x=15$

$[64/64*a^2+(((55344+16*729)/64) mod (729))*a+(((11964681+15*729)/64) mod (729))] mod (729) = 0$

$(a^2+318*a+495) mod (729) = 0$

Applying the Coppersmith univariate method

$->$ $a=3$ $->$ $q=43$

Improve this question
$\endgroup$
3
  • $\begingroup$ @kelalaka not RSA attack $\endgroup$
    – Alberico Lepore
    Jan 26, 2022 at 14:28
  • 1
    $\begingroup$ Ah, I see. github.com/defund/coppersmith, no easy to convert to C/GNU/GMP. May be you can benefit from NTL on your progress. $\endgroup$
    – kelalaka
    Jan 26, 2022 at 14:54
  • $\begingroup$ @kelalaka thank you! I will try to learn over the years $\endgroup$
    – Alberico Lepore
    Jan 26, 2022 at 15:46

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.