Hi all,<br>I don't know if i am in the good section to post this thread but let's see my problem !<br><br>For a crypto tool i need to implement euclide algorithm. and I want to set "q" in a table.<br><br>
With small numbers, no problem all "q" are corrects, but the problem if i use it with big numbers (1024, 2048bit), any errors appear.<br><br>My algorithm :<br><br>void my_euclide(mpz_t a, mpz_t b)<br>{<br> int i, last;<br>
mpz_t r, q ;<br> mpz_t tab[400];<br><br> mpz_init(q);<br> <br>//r not null to begin<br> mpz_init_set_str(r, "1", 10);<br><br> printf("Euclide...\n");<br><br> for (i = 0; (i < 400) && (mpz_sgn(r) != 0); i++)<br>
{<br> mpz_fdiv_qr (q, r, a, b); <br> mpz_init(tab[i]);<br> mpz_set(tab[i], q);<br> if (mpz_sgn(r) == 0)<br> {<br> last = i + 1;<br> break;<br> } <br> mpz_set(a,b);<br>
mpz_set(b,r);<br> }<br><br> print_fcont(tab, last); // draw table of "q"<br><br>I use it with a = 3577287383116883468500617249491494675927718321983420550518569067452761680640387244979254846438842585885931908143222535744998469152280919771846695625950405614788715975354132866614664695968729810535189<br>
and <br>b = 100000000000000000000000000000000000000000010767242835355448074805523947143544456915045792940521295313114592588491876390386483430760373697739129050551823109117659650273528892669222396247822205155889979<br><br>
result with the upper algorithm :<br><br>[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<br>,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<br>,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,<b>1,5,6<br>
,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,<br>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,<br>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,<br>
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,<br>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<br>,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<br>
,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<br>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,</b>]<br><br>The good result :<br>[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<br>
, 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<br>, 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, <b>2, 7, 1<br>
, 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<br>, 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<br>
, 1, 3, 4, 2, 1, 1, 1, 1, 6, 3, 1, 3, 1, 2, 1, 5, 1, . . .</b>]<br><br>In bold no match found !<br><br>The algorithm looks like good so .. maybe gmplib does not allocate good values of a and b ? or division ....<br><br>If you have any ideas..<br>
<br>Thank you for your help.<br><br>Have a good day.<br><br>David L.<br>