ここに、Ben Lynn blynn @ githubによるこのLGPLコードに基づくコード(C + GMP)があります。スタンフォードオブガーナーアルゴリズム(クエリガーナーmpz_tによるRIP Googleコード検索で見つかりました):
https ://github.com/blynn/pbc/blob/master/guru/indexcalculus.c
(彼のPBC(ペアリングベースの暗号)の一部)図書館)
でコンパイルしgcc -std=c99 -lgmp
ます。また、ケースのサイズを変更してください。
#include <gmp.h>
#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>
// Garner's Algorithm.
// See Algorithm 14.71, Handbook of Cryptography.
// x - result v residuals m - primes t-size of vectors
static void CRT(mpz_t x, mpz_ptr *v, mpz_ptr *m, int t) {
mpz_t u;
mpz_t C[t];
int i, j;
mpz_init(u);
for (i=1; i<t; i++) {
mpz_init(C[i]);
mpz_set_ui(C[i], 1);
for (j=0; j<i; j++) {
mpz_invert(u, m[j], m[i]);
mpz_mul(C[i], C[i], u);
mpz_mod(C[i], C[i], m[i]);
}
}
mpz_set(u, v[0]);
mpz_set(x, u);
for (i=1; i<t; i++) {
mpz_sub(u, v[i], x);
mpz_mul(u, u, C[i]);
mpz_mod(u, u, m[i]);
for (j=0; j<i; j++) {
mpz_mul(u, u, m[j]);
}
mpz_add(x, x, u);
}
for (i=1; i<t; i++) mpz_clear(C[i]);
mpz_clear(u);
}
const int size=6; // Change this please
int main()
{
mpz_t res;
mpz_ptr t[size], p[size];
for(int i=0;i<size;i++) {
t[i]=(mpz_ptr)malloc(sizeof(mpz_t));
p[i]=(mpz_ptr)malloc(sizeof(mpz_t));
mpz_init(p[i]);
mpz_init(t[i]);
}
mpz_init(res);
for(int i=0;i<size;i++){
unsigned long rr,pp;
scanf("%*c%*c%*c = %lu (%% %lu)\n",&rr,&pp);
printf("Got %lu res on mod %% %lu \n",rr,pp);
mpz_set_ui(p[i],pp);
mpz_set_ui(t[i],rr);
}
CRT(res,t,p,size);
gmp_printf("N = %Zd\n", res);
}
例は解決されました:
$ ./a.out
r_1 = 1246736738 (% 2147483743)
r_2 = 748761 (% 2147483713)
r_3 = 1829651881 (% 2147483693)
r_4 = 2008266397 (% 2147483659)
r_5 = 748030137 (% 2147483647)
r_6 = 1460049539 (% 2147483629)
Got 1246736738 res on mod % 2147483743
Got 748761 res on mod % 2147483713
Got 1829651881 res on mod % 2147483693
Got 2008266397 res on mod % 2147483659
Got 748030137 res on mod % 2147483647
Got 1460049539 res on mod % 2147483629
N = 703066055325632897509116263399480311
Nは703066055325632897509116263399480311です