mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2011-06-08, 13:53   #1
prss
 
prss's Avatar
 
Jun 2011
Brazil

268 Posts
Question factoring with MIRACL library

Hi,
I started to study ECM factoring implemented by Alpetron: http://www.alpertron.com.ar/ECM.HTM
I need implement Alpetron ECM factoring using MIRACL library for school work. However,
i dont know as works LargeMontgomeryMult method, i.e, need understand LargeMontgomeryMult method for implement that method in MIRACL library.
I would like that someone help me implement method in MIRACL library (http://www.shamus.ie/uploads/File/miracl3.zip).
if anyone wants i already have a DevCpp project configured for use MIRACL library. The LargeMontgomeryMult method can be found in http://www.alpertron.com.ar/ecm.zip - file ecm.java:line 5379.
I already tried use functions nres_modmult, nres, redc from MIRACL but not produces same result that LargeMontgomeryMult.
Thank you in advance!
prss is offline   Reply With Quote
Old 2011-06-08, 18:05   #2
prss
 
prss's Avatar
 
Jun 2011
Brazil

2·11 Posts
Default

Plz, help me to know that operation LargeMontgomeryMult method execute on Nbr1 and Nbr2, such that Nbr1 and Nbr2 are in format described in method BigNbrToBigInt and BigInteger is a java class.

Code:
void LargeMontgomeryMult(int Nbr1[], int Nbr2[], int Prod[]) {
    long Pr, Nbr, MontDig;
    long Prod0, Prod1, Prod2, Prod3, Prod4, Prod5, Prod6, Prod7, Prod8, Prod9, Prod10;
    Prod0 = Prod1 = Prod2 = Prod3 = Prod4 = Prod5 = Prod6 = Prod7 = Prod8 = Prod9 = Prod10 = 0;
    long TestNbr0 = TestNbr[0];
    long TestNbr1 = TestNbr[1];
    long TestNbr2 = TestNbr[2];
    long TestNbr3 = TestNbr[3];
    long TestNbr4 = TestNbr[4];
    long TestNbr5 = TestNbr[5];
    long TestNbr6 = TestNbr[6];
    long TestNbr7 = TestNbr[7];
    long TestNbr8 = TestNbr[8];
    long TestNbr9 = TestNbr[9];
    long TestNbr10 = TestNbr[10];
    long Nbr2_0 = Nbr2[0];
    long Nbr2_1 = Nbr2[1];
    long Nbr2_2 = Nbr2[2];
    long Nbr2_3 = Nbr2[3];
    long Nbr2_4 = Nbr2[4];
    long Nbr2_5 = Nbr2[5];
    long Nbr2_6 = Nbr2[6];
    long Nbr2_7 = Nbr2[7];
    long Nbr2_8 = Nbr2[8];
    long Nbr2_9 = Nbr2[9];
    long Nbr2_10 = Nbr2[10];
    int j;
    for (j = 11; j < NumberLength; j++) {
        Prod[j] = 0;
    }
    for (int i = 0; i < NumberLength; i++) {
        Pr = (Nbr = Nbr1[i]) * Nbr2_0 + Prod0;
        MontDig = ((int) Pr * MontgomeryMultN) & 0x7FFFFFFFL;
        Prod0 = (Pr = ((MontDig * TestNbr0 + Pr) >>> 31) + MontDig * TestNbr1 + Nbr * Nbr2_1 + Prod1) & 0x7FFFFFFFL;
        Prod1 = (Pr = (Pr >>> 31) + MontDig * TestNbr2 + Nbr * Nbr2_2 + Prod2) & 0x7FFFFFFFL;
        Prod2 = (Pr = (Pr >>> 31) + MontDig * TestNbr3 + Nbr * Nbr2_3 + Prod3) & 0x7FFFFFFFL;
        Prod3 = (Pr = (Pr >>> 31) + MontDig * TestNbr4 + Nbr * Nbr2_4 + Prod4) & 0x7FFFFFFFL;
        Prod4 = (Pr = (Pr >>> 31) + MontDig * TestNbr5 + Nbr * Nbr2_5 + Prod5) & 0x7FFFFFFFL;
        Prod5 = (Pr = (Pr >>> 31) + MontDig * TestNbr6 + Nbr * Nbr2_6 + Prod6) & 0x7FFFFFFFL;
        Prod6 = (Pr = (Pr >>> 31) + MontDig * TestNbr7 + Nbr * Nbr2_7 + Prod7) & 0x7FFFFFFFL;
        Prod7 = (Pr = (Pr >>> 31) + MontDig * TestNbr8 + Nbr * Nbr2_8 + Prod8) & 0x7FFFFFFFL;
        Prod8 = (Pr = (Pr >>> 31) + MontDig * TestNbr9 + Nbr * Nbr2_9 + Prod9) & 0x7FFFFFFFL;
        Prod9 = (Pr = (Pr >>> 31) + MontDig * TestNbr10 + Nbr * Nbr2_10 + Prod10) & 0x7FFFFFFFL;
        Prod10 = (Pr = (Pr >>> 31) + MontDig * TestNbr[11] + Nbr * Nbr2[11] + Prod[11]) & 0x7FFFFFFFL;
        for (j = 12; j < NumberLength; j++) {
            Prod[j - 1] = (int) ((Pr = (Pr >>> 31) + MontDig * TestNbr[j] + Nbr * Nbr2[j] + Prod[j]) & 0x7FFFFFFFL);
        }
        Prod[j - 1] = (int) (Pr >>> 31);
    }
    Prod[0] = (int) Prod0;
    Prod[1] = (int) Prod1;
    Prod[2] = (int) Prod2;
    Prod[3] = (int) Prod3;
    Prod[4] = (int) Prod4;
    Prod[5] = (int) Prod5;
    Prod[6] = (int) Prod6;
    Prod[7] = (int) Prod7;
    Prod[8] = (int) Prod8;
    Prod[9] = (int) Prod9;
    Prod[10] = (int) Prod10;
    for (j = NumberLength - 1; j >= 0; j--) {
        if (Prod[j] != TestNbr[j]) {
            break;
        }
    }
    if (j < 0 || j >= 0 && Prod[j] >= TestNbr[j]) {
        Pr = 0;
        for (j = 0; j < NumberLength; j++) {
            Prod[j] = (int) ((Pr = (Pr >> 31) + (long) Prod[j] - (long) TestNbr[j]) & 0x7FFFFFFFL);
        }
    }
}    
void GetMontgomeryParms() {
    int N, x, j;
    dN = (double) TestNbr[NumberLength - 1];
    if (NumberLength > 1) {
        dN += (double) TestNbr[NumberLength - 2] / dDosALa31;
    }
    if (NumberLength > 2) {
        dN += (double) TestNbr[NumberLength - 3] / dDosALa62;
    }
    x = N = (int) TestNbr[0];
    x = x * (2 - N * x);
    x = x * (2 - N * x);
    x = x * (2 - N * x);
    x = x * (2 - N * x);
    MontgomeryMultN = (-x) & 0x7FFFFFFF;
    j = NumberLength;
    MontgomeryMultR1[j] = 1;
    do {
        MontgomeryMultR1[--j] = 0;
    } while (j > 0);
    AdjustModN(MontgomeryMultR1, TestNbr, NumberLength);
    MultBigNbrModN(MontgomeryMultR1, MontgomeryMultR1, MontgomeryMultR2, TestNbr, NumberLength);
    MontgomeryMult(MontgomeryMultR2, MontgomeryMultR2, MontgomeryMultAfterInv);
    AddBigNbrModN(MontgomeryMultR1, MontgomeryMultR1, MontgomeryMultR2, TestNbr, NumberLength);
}
static void Convert32To31Bits(long[] nbr32bits, int[] nbr31bits, int NumberLength) {
    int i, j, k;
    j = 0;
    nbr32bits[NumberLength] = 0;
    for (i = 0; i < NumberLength; i++) {
        k = i & 0x0000001F;
        if (k == 0) {
            nbr31bits[i] = (int) (nbr32bits[j] & 0x7FFFFFFF);
        } else {
            nbr31bits[i] = (int) (((nbr32bits[j] >> (32 - k)) | (nbr32bits[j + 1] << k)) & 0x7FFFFFFF);
            j++;
        }
    }
}
static int BigNbrToBigInt(BigInteger N, int TestNbr[]) {
    byte[] Result;
    long[] Temp;
    int i, j, mask;
    long p;
    int NumberLength;
    Result = N.toByteArray();
    NumberLength = (Result.length * 8 + 30) / 31;
    Temp = new long[NumberLength + 1];
    j = 0;
    mask = 1;
    p = 0;
    for (i = Result.length - 1; i >= 0; i--) {
        p += mask * (long) (Result[i] >= 0 ? Result[i] : Result[i] + 256);
        mask <<= 8;
        if (mask == 0) { // Overflow
            Temp[j++] = p;
            mask = 1;
            p = 0;
        }
    }
    Temp[j] = p;
    Convert32To31Bits(Temp, TestNbr, NumberLength);
    if (TestNbr[NumberLength - 1] > 1000000000) {
        TestNbr[NumberLength] = 0;
        NumberLength++;
    }
    TestNbr[NumberLength] = 0;
    return NumberLength;
}
prss is offline   Reply With Quote
Old 2011-06-08, 19:20   #3
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

13·107 Posts
Default

The code in the applet is optimized so it will be difficult to understand. I think it is better for you to study ECM and Montgomery multiplication and code your own implementation instead of copying code written by other people. You can read the ECM implementation notes I wrote several years ago on the Mersenne Wiki at: http://www.mersennewiki.org/index.php/ECM
alpertron is offline   Reply With Quote
Old 2011-06-08, 20:11   #4
prss
 
prss's Avatar
 
Jun 2011
Brazil

1616 Posts
Default

Thanks for responding.
I would like very study better ECM and Montgomery Multiplication but i dont have time in moment.
I need just know that operation LargeMontgomeryMult(a,b,c) method perform.
Ex: if a * b mod c or if a/b mod c, a * b * MontgomeryMultN ^ (-1) mod c, ...
Plz, explain me in resume.
Thank you in advance.
prss is offline   Reply With Quote
Old 2011-06-08, 20:18   #5
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

13·107 Posts
Default

Quote:
Originally Posted by prss View Post
Thanks for responding.
I would like very study better ECM and Montgomery Multiplication but i dont have time in moment.
I need just know that operation LargeMontgomeryMult(a,b,c) method perform.
Ex: if a * b mod c or if a/b mod c, a * b * MontgomeryMultN ^ (-1) mod c, ...
Plz, explain me in resume.
Thank you in advance.
a and b are the factors in Montgomery space, c is the product (the array where the result of the function will be stored) in Montgomery space and TestNbr (a global variable) is the modulus.
alpertron is offline   Reply With Quote
Old 2011-06-08, 20:28   #6
prss
 
prss's Avatar
 
Jun 2011
Brazil

2·11 Posts
Default

What is function of the MontgomeryMultN in product a by b?
prss is offline   Reply With Quote
Old 2011-06-08, 20:36   #7
em99010pepe
 
em99010pepe's Avatar
 
Sep 2004

2×5×283 Posts
Default

O que você quer requer um nível avançado de compreensão matemática que creio que você não tem. Esse suposto trabalho de casa é para a universidade? Que idade tem? Qual o seu nível académico?
em99010pepe is offline   Reply With Quote
Old 2011-06-08, 20:59   #8
prss
 
prss's Avatar
 
Jun 2011
Brazil

2×11 Posts
Default

Tenho 25 anos, sou bacharel em Ciência da Computação, esse trabalho servirá como base para a minha futura tese de mestrado em fatoração de inteiros. Por isso, quero testar a eficiência da implementação do Alpertron com a MIRACL. Já estudei superficialmente este paper http://web.itu.edu.tr/~orssi/dersler/cryptography/Montgomery.pdf . Mas, no momento, estou pensando só na performance da implementação com a biblioteca. Depois, pretendo me aprofundar teoricamente.
prss is offline   Reply With Quote
Old 2011-06-08, 21:05   #9
em99010pepe
 
em99010pepe's Avatar
 
Sep 2004

2·5·283 Posts
Default

Nesse caso sugiro que estude com mais profundidade a teoria e que vá pedindo aqui direcções de artigos publicados. Se não tiver conhecimento de causa será aqui enxovalhado pela sua ignorância. Portanto vá pedindo textos para estudar.
Depois da teoria estar bem assente comece a colocar as suas questões que aqui o pessoal lhe vai ajudar a percorrer o caminho que pretende sem nunca lhe dar a papinha feita.
em99010pepe is offline   Reply With Quote
Old 2011-06-08, 21:12   #10
em99010pepe
 
em99010pepe's Avatar
 
Sep 2004

2×5×283 Posts
Default

I'm just guiding prss in his/her native language...

Last fiddled with by em99010pepe on 2011-06-08 at 21:12
em99010pepe is offline   Reply With Quote
Old 2011-06-08, 21:13   #11
prss
 
prss's Avatar
 
Jun 2011
Brazil

2×11 Posts
Default

Certo. Então que texto você me recomendaria para eu entender como é feita a multiplicação de Montgomery no código do Alpertron?
prss is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Using YAFU as a C-library LangerJan YAFU 2 2013-02-17 06:18
Quickest fft library nuggetprime Software 3 2011-01-09 01:24
CURL library error Glenn Leider Software 12 2009-04-16 02:45
GWNUM library and llr leizhoucn Programming 2 2007-11-05 09:34
GWNUM library bearnol Software 6 2006-02-24 11:19

All times are UTC. The time now is 00:05.


Wed Dec 8 00:05:37 UTC 2021 up 137 days, 18:34, 0 users, load averages: 2.58, 2.46, 2.36

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.