[GMP implementation] algorithm Euclide

[icksss]

Hi all,
I don't know if i am in the good section to post this thread but let's see
my problem !

For a crypto tool i need to implement euclide algorithm. and I want to set
"q" in a table.

With small numbers, no problem all "q" are corrects, but the problem if i
use it with big numbers (1024, 2048bit), any errors appear.

My algorithm :

void my_euclide(mpz_t a, mpz_t b)
{
 int i, last;
 mpz_t  r, q ;
 mpz_t tab[400];

 mpz_init(q);

//r not null to begin
 mpz_init_set_str(r, "1", 10);

 printf("Euclide...\n");

 for (i = 0; (i < 400) && (mpz_sgn(r) != 0); i++)
   {
     mpz_fdiv_qr (q, r, a, b);
     mpz_init(tab[i]);
     mpz_set(tab[i], q);
     if (mpz_sgn(r) == 0)
       {
         last = i + 1;
         break;
       }
       mpz_set(a,b);
       mpz_set(b,r);
   }

 print_fcont(tab, last); // draw table of "q"

I use it with a =
3577287383116883468500617249491494675927718321983420550518569067452761680640387244979254846438842585885931908143222535744998469152280919771846695625950405614788715975354132866614664695968729810535189
and
b =
100000000000000000000000000000000000000000010767242835355448074805523947143544456915045792940521295313114592588491876390386483430760373697739129050551823109117659650273528892669222396247822205155889979

result with the upper algorithm :

[0,27,1,20,1,4,5,1,15,1,1,1,2,1,3,1,1,29,1,2,1,1,2,1,1,2,1,2,3,2,1,3,1,2,1,1,1,5
,1,2400,7,2,1,46,1,1,3,1,1,1,11,1,16,54,1,1,1,1,7,1,1,10,1,1,1,7,19,9,1,10,3,1,3
,1,1,1,1,1,1,30,1,2,1,19,5,1,2,1,1,1,1,5,1,1,1,5,1,4,25,1,3,1,3,1,1,7,1,14,*
1,5,6
,8,2,4,4,5,3,2,6,1,13,2,2,1,14,1,4,1,9,3,8,7,2,9,6,1,1,1,1,2,1,1,3,3,1,41,2,6,6,
6,3,2,1,2,1,230,8,12,5,1,3,1,1,99,1,4,5,2,7,5,4,1,16,1,4,40,1,3,4,1,4,1,2,1,1,6,
1,1,4,5,4,4,3,5,2,8,1,9,1,1,10,1,2,1,1,2,1,3,11,3,7,1,2,3,1,2,285,3,4,2,1,1,1,7,
1,2,2913,1,1,4,1,3,5,3,1,1,2,1,2,2,1,27,1,1,4,10,2,4,7,1,1,20,4,43,4,1,1,2,60,1,
29,1,2,1,2,3,1,3,1,1,4,1,1,1,1,3,1,1,12,1,2,1,12,4,2,2,26,14,3,1,1,6,1,3,1,1,6,1
,1,20,1,2,8,1,7,3,69,1,16,1,1,1,2,1,1,1,2,5,1,9,1,1,17,6,14,19,2,1,1,1,2,3,6,3,2
,1,1,3,7,4,1,3,1,1,1,4,6,1,1,2,1,1,1,2,2,1,1,3,1,2,1,1,93,8,1,3,4,1,1,1,5,18,1,2
9,1,7,1,5,1,3,4,1,1,3,2,1,6,3,1,2,1,2,3,1,29,14,3,1,7,2,*]

The good result :
[0, 27, 1, 20, 1, 4, 5, 1, 15, 1, 1, 1, 2, 1, 3, 1, 1, 29, 1, 2, 1, 1, 2, 1,
1, 2, 1, 2, 3, 2, 1, 3, 1, 2, 1, 1, 1, 5
, 1, 2400, 7, 2, 1, 46, 1, 1, 3, 1, 1, 1, 11, 1, 16, 54, 1, 1, 1, 1, 7, 1,
1, 10, 1, 1, 1, 7, 19, 9, 1, 10, 3, 1, 3
, 1, 1, 1, 1, 1, 1, 30, 1, 2, 1, 19, 5, 1, 2, 1, 1, 1, 1, 5, 1, 1, 1, 5, 1,
4, 25, 1, 3, 1, 3, 1, 1, 7, 1, 14, *2, 7, 1
, 11, 4, 1, 3, 1, 1, 1, 3, 3, 8, 1, 4, 1, 2, 2, 2, 2, 1, 1, 1, 1, 1, 5, 22,
1, 2, 4, 1, 22, 1, 4, 2, 1, 15, 1, 1, 10, 4
, 66, 6, 3, 3, 2, 2, 36, 1, 1, 1, 1, 48, 2, 2, 13, 1, 1, 1, 2, 1, 10, 2, 1,
1, 2, 5, 1, 29, 1, 12, 1, 56, 11, 147867491
, 1, 3, 4, 2, 1, 1, 1, 1, 6, 3, 1, 3, 1, 2, 1, 5, 1, . . .*]

In bold no match found !

The algorithm looks like good so .. maybe gmplib does not allocate good
values of a and b ? or division ....

If you have any ideas..

Thank you for your help.

Have a good day.

David L.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://gmplib.org/list-archives/gmp-discuss/attachments/20080619/c04dbdd4/attachment.html