Hi
Just installed MPIR and am playing with it, and my program crashed
for some unknown reason.
So I did a valgrind and found on a relatively simple program I get
an invalid memory read. Given that this is likely to result from my
misunderstanding of something. I am posting here so someone
can help me out (either my install is wrong, or my application is wrong)....
OK. Here is some code which reproduces the bug (its for a mod square
root algorithm)....
- The typedef of mpz_class to bigint is because I am comparing this
MPIR implementation against the same one with another bignum class
provider
#include <mpirxx.h>
#include <iostream>
using namespace std;
typedef mpz_class bigint;
bigint sqrRootMod(const bigint& a,const bigint& p)
{
bigint ans;
if (a==0) { ans=0; return ans; }
if (mpz_tstbit(p.get_mpz_t(),1)==1)
{ // First do case with p=3 mod 4
bigint exp=(p+1)/4;
mpz_powm(ans.get_mpz_t(),a.get_mpz_t(),exp.get_mpz_t(),p.get_mpz_t());
}
else
{ // Shanks algorithm
gmp_randclass Gen(gmp_randinit_default);
Gen.seed(0);
bigint x,y,n,q,t,b,temp;
// Find n such that (n/p)=-1
int leg=1;
while (leg!=-1)
{ n=Gen.get_z_range(p);
leg=mpz_legendre(n.get_mpz_t(),p.get_mpz_t());
}
// Split p-1 = 2^e q
q=p-1;
int e=0;
while (mpz_even_p(q.get_mpz_t()))
{ e++; q=q/2; }
// y=n^q mod p, x=a^((q-1)/2) mod p, r=e
int r=e;
mpz_powm(y.get_mpz_t(),n.get_mpz_t(),q.get_mpz_t(),p.get_mpz_t());
temp=(q-1)/2;
mpz_powm(x.get_mpz_t(),a.get_mpz_t(),temp.get_mpz_t(),p.get_mpz_t());
// b=a*x^2 mod p, x=a*x mod p
b=(a*x*x)%p;
x=(a*x)%p;
// While b!=1 do
while (b!=1)
{ // Find smallest m such that b^(2^m)=1 mod p
int m=1;
temp=(b*b)%p;
while (temp!=1)
{ temp=(temp*temp)%p; m++; }
// t=y^(2^(r-m-1)) mod p, y=t^2, r=m
t=y;
for (int i=0; i<r-m-1; i++)
{ t=(t*t)%p; }
y=(t*t)%p;
r=m;
// x=x*t mod p, b=b*y mod p
x=(x*t)%p;
b=(b*y)%p;
}
ans=x;
}
return ans;
}
int main()
{
mpz_class a,b,p;
b=3; p=17;
a=(b*b)%p;
b=sqrRootMod(a,p);
cout << b << endl;
}
Now on compiling this (g++ -g blah.cpp -lmpirxx -lmpir) and then doing
valgrind I get...
mpir% valgrind --leak-check=yes a.out
==7827== Memcheck, a memory error detector
==7827== Copyright (C) 2002-2009, and GNU GPL'd, by Julian Seward et al.
==7827== Using Valgrind-3.5.0 and LibVEX; rerun with -h for copyright info
==7827== Command: a.out
==7827==
==7827== Invalid read of size 8
==7827== at 0x4E6C1AD: __gmpn_copyi (in
/home/crypto/linux.x86_64/mpir-2.5.1/lib/libmpir.so.7.4.2)
==7827== by 0x40138A: sqrRootMod(__gmp_expr<__mpz_struct [1], __mpz_struct
[1]> const&, __gmp_expr<__mpz_struct [1], __mpz_struct [1]> const&)
(test.cpp:35)
==7827== by 0x401D30: main (test.cpp:71)
==7827== Address 0x50e40d8 is 0 bytes after a block of size 8 alloc'd
==7827== at 0x4A0515D: malloc (vg_replace_malloc.c:195)
==7827== by 0x4E1B078: __gmp_default_allocate (in
/home/crypto/linux.x86_64/mpir-2.5.1/lib/libmpir.so.7.4.2)
==7827== by 0x4E2A8D7: __gmpz_init (in
/home/crypto/linux.x86_64/mpir-2.5.1/lib/libmpir.so.7.4.2)
==7827== by 0x402065: __gmp_expr<__mpz_struct [1], __mpz_struct
[1]>::__gmp_expr() (mpirxx.h:1546)
==7827== by 0x401136: sqrRootMod(__gmp_expr<__mpz_struct [1], __mpz_struct
[1]> const&, __gmp_expr<__mpz_struct [1], __mpz_struct [1]> const&)
(test.cpp:21)
==7827== by 0x401D30: main (test.cpp:71)
==7827==
14
==7827==
==7827== HEAP SUMMARY:
==7827== in use at exit: 0 bytes in 0 blocks
==7827== total heap usage: 51 allocs, 51 frees, 23,898 bytes allocated
==7827==
==7827== All heap blocks were freed -- no leaks are possible
==7827==
==7827== For counts of detected and suppressed errors, rerun with: -v
==7827== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 6 from 6)
--
You received this message because you are subscribed to the Google Groups
"mpir-devel" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/mpir-devel/-/Kr_PtO4mPrIJ.
To post to this group, send email to mpir-devel@googlegroups.com.
To unsubscribe from this group, send email to
mpir-devel+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/mpir-devel?hl=en.
