undefined inverse in _ntl_zinvmod

Hi all, I have been working on the program here. However, I am getting the error undefined inverse in _ntl_zinvmod when I run the program after I apply the Chinese Remainder Theorem by Number Theory Library. Any help is much appreciated! Thank you

#include <iostream>
#include <NTL/ZZ.h>
#include <NTL/RR.h>
#include <NTL/vec_ZZ.h>
#include <NTL/lip.h>
#include <NTL/ctools.h>
#include <stdlib.h>
#include <stdio.h>
#include <cmath>



using namespace std;
using namespace NTL;

void gen_rprime(ZZ& p1, ZZ& p2, ZZ& p3, ZZ& p4, ZZ& p5, ZZ& n, ZZ& dp1, ZZ& dp2, ZZ& dp3, ZZ& dp4, ZZ& dp5, const long ModBitSize) {
ZZ p1_, p2_, p3_, p4_, p5_, n1_, n2_, n3_, k1_, k2_, k3_, k4_, k5_, k6_, k7_, k8_, a_tmp1, a_tmp2, p_tmp1, p_tmp2; //temporary variables
long PrimeBitSize = ModBitSize/5; //Bit length of primes are one fifth of the modulus's bit length
SetSeed(to_ZZ(time(NULL)));

for(; ;){
k1_ = to_ZZ(20); // Let k1_ = 20
GenPrime(p1, PrimeBitSize); // Generate prime p1
GenPrime(p2, PrimeBitSize); // Generate prime p2
GenPrime(p3, PrimeBitSize); // Generate prime p3
GenPrime(p4, PrimeBitSize); // Generate prime p4
GenPrime(p5, PrimeBitSize); // Generate prime p5
sub(p1_, p1, 1); // p1_ = p1 - 1
sub(p2_, p2, 1); // p2_ = p2 - 1
sub(p3_, p3, 1); // p3_ = p3 - 1
sub(p4_, p4, 1); // p4_ = p4 - 1
sub(p5_, p5, 1); // p5_ = p5 - 1
mul(n1_, p1, p2); // n1_ = p1*p2
mul(n2_, n1_, p3); // n2_ = p1*p2*p3
mul(n3_, n2_, p4); // n3_ = p1*p2*p3*p4
mul(n, n3_, p5); // n = p1*p2*p3*p4*p5
k2_ = to_ZZ(5); // Let k2_ = 5
k3_ = GCD((GCD((GCD((GCD(p1_, p2_)), p3_)), p4_)), p5_); // k3_ is the GCD of all 5 primes
if (k3_ == to_ZZ(2)) break; // If the GCD = 2, break
}

RandomBits(dp1, PrimeBitSize); // Generate dp1
k4_ = dp1%2; // Find parity of dp1
RandomBits(dp2, PrimeBitSize); // Generate dp2
k5_ = dp2%2; // Find parity of dp2
if (k4_ == k5_) { dp2 = dp2; } // Make sure that the parity of dp1 = dp2
else if (k4_ != k5_) { dp2 = dp2 - 1; } // Make sure that the parity of dp1 = dp2
RandomBits(dp3, PrimeBitSize); // Generate dp3
k6_ = dp3%2; // Find parity of dp3
if (k4_ == k6_) { dp3 = dp3; } // Make sure that the parity of dp1 = dp3
else if (k4_ != k6_) { dp3 = dp3 -1; } // Make sure that the parity of dp1 = dp3
RandomBits(dp4, PrimeBitSize); // Generate dp4
k7_ = dp4%2; // Find parity of dp4
if (k4_ == k7_) { dp4 = dp4; } // Make sure that the parity of dp1 = dp4
else if (k4_ != k7_) { dp4 = dp4 -1; } // Make sure that the parity of dp1 = dp4
RandomBits(dp5, PrimeBitSize); // Generate dp5
k8_ = dp5%2; // Find parity of dp5
if (k4_ == k8_) { dp5 = dp5; } // Make sure that the parity of dp1 = dp5
else if (k4_ != k8_) { dp5 = dp5 -1; } // Make sure that the parity of dp1 = dp5

if (((GCD(dp1, p1_)) == to_ZZ(1)) && ((dp1%2)==k4_) && 1<dp1<p1) dp1 = dp1;
else for (; ;) {
dp1 = to_ZZ(0);
RandomBits(dp1, PrimeBitSize);
if (((GCD(dp1, p1_)) == to_ZZ(1)) && ((dp1%2)==k4_)&& 1<dp1<p1) break;
}

if (((GCD(dp2, p2_)) == to_ZZ(1)) && ((dp2%2)==k4_)&& 1<dp2<p2) dp2 = dp2;
else for (; ;) {
dp2 = to_ZZ(0);
RandomBits(dp2, PrimeBitSize);
if (((GCD(dp2, p2_)) == to_ZZ(1)) && ((dp2%2)==k4_)&& 1<dp2<p2) break;
}
if (((GCD(dp3, p3_)) == to_ZZ(1)) && ((dp3%2)==k4_)&& 1<dp3<p3) dp3 = dp3;
else for (; ;) {
dp3 = to_ZZ(0);
RandomBits(dp3, PrimeBitSize);
if (((GCD(dp3, p1_)) == to_ZZ(1)) && ((dp3%2)==k4_)&& 1<dp3<p3) break;
}
if (((GCD(dp4, p4_)) == to_ZZ(1)) && ((dp4%2)==k4_)&& 1<dp4<p4) dp4 = dp4;
else for (; ;) {
dp4 = to_ZZ(0);
RandomBits(dp4, PrimeBitSize);
if (((GCD(dp4, p4_)) == to_ZZ(1)) && ((dp4%2)==k4_)&& 1<dp4<p4) break;
}
if (((GCD(dp5, p5_)) == to_ZZ(1)) && ((dp5%2)==k4_)&& 1<dp5<p5) dp5 = dp5;
else for (; ;) {
dp5 = to_ZZ(0);
RandomBits(dp5, PrimeBitSize);
if (((GCD(dp5, p5_)) == to_ZZ(1)) && ((dp5%2)==k4_)&& 1<dp5<p5) break;
}
}
ZZ solveByCRT(vec_ZZ& primes, vec_ZZ& a, int num_of_primes){
int i;
long check;
ZZ a_tmp1, a_tmp2, p_tmp1, p_tmp2;

for(i=0; i<(5-1); i++){
if(i==0) a_tmp1 = a[i];
a_tmp2 = a[i+1];
if(i==0) p_tmp1 = primes[i]-1;
p_tmp2 = primes[i+1]-1;
check = CRT(a_tmp1, p_tmp1, a_tmp2, p_tmp2); //a_tmp1 is updated with the intermediate solution

}

//p_tmp1 is updated with p_tmp1*p_tmp2

return a_tmp1; //Returns the final solution

}

int main(){
ZZ p1, p2, p3, p4, p5, n, dp1, dp2, dp3, dp4, dp5;
long ModBitSize;
SetSeed(to_ZZ(time(NULL)));
ModBitSize = 1000;
gen_rprime(p1, p2, p3, p4, p5, n, dp1, dp2, dp3, dp4, dp5, ModBitSize);
cout << "The first prime (p1) is: " << p1 << endl;
cout << "The second prime (p2) is: " << p2 << endl;
cout << "The third prime (p3) is: " << p3 << endl;
cout << "The fourth prime (p4) is: " << p4 << endl;
cout << "The fifth prime (p5) is: " << p5 << endl;
cout << "Their product (n) is: " << n << endl;
cout << "DP1 is: " << dp1 << endl;
cout << "DP2 is: " << dp2 << endl;
cout << "DP3 is: " << dp3 << endl;
cout << "DP4 is: " << dp4 << endl;
cout << "DP5 is: " << dp5 << endl;


ZZ soln; //Stores the solution to the system of equations
vec_ZZ a, primes;
a.SetLength(5); //After declaring variables of vec_ZZ type, we always
primes.SetLength(5); //need to set the length of the vectors. In this case,
//there are 3 primes, so length is 3.
a[0] = dp1; //U can try out for different numbers of primes
a[1] = dp2; //with different values of a[i]
a[2] = dp3;
a[3] = dp4;
a[4] = dp5;

primes[0] = p1; //Need to set the values of the vectors "a" and "primes"
primes[1] = p2;
primes[2] = p3;
primes[3] = p4;
primes[4] = p5;

soln = solveByCRT(primes, a, 5);


//For illustration purposes:
//cout <<"x = " << a[0] << "(mod " << primes[0] << ")" << endl;
//cout <<"x = " << a[1] << "(mod " << primes[1] << ")" << endl;
//cout <<"x = " << a[2] << "(mod " << primes[2] << ")" << endl;
//cout <<"x = " << a[3] << "(mod " << primes[3] << ")" << endl;
//cout <<"x = " << a[4] << "(mod " << primes[4] << ")" << endl;

cout << "d= "<< soln << endl;

system ("pause");
return 0;

}
Topic archived. No new replies allowed.