Re: GSOC Introduction

[Martin Albrecht]

Hey Siddharth,

great to hear you're interested. It would be best if you could play around
with LELA a bit and provide a small patch to see if it works for you?

For example, you could take two std::vector of mod p matrices and consider
these vectors as matrices with polynomial entries. Then, you could perform
schoolbook quadratic polynomial multiplication on these polynomials and take
the result modulo some minimal polynomial represented as a std::vector<int>
(or so).

Something like that.

Cheers,
Martin

--
name: Martin Albrecht
_pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99
_otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF
_www: http://martinralbrecht.wordpress.com/
_jab: martinr...@jabber.ccc.de

[Burcin Erocal]

Hi Siddharth,

On Sun, 21 Apr 2013 10:41:18 +0100
Martin Albrecht <martinr...@googlemail.com> wrote:

> For example, you could take two std::vector of mod p matrices and
> consider these vectors as matrices with polynomial entries. Then, you
> could perform schoolbook quadratic polynomial multiplication on these
> polynomials and take the result modulo some minimal polynomial
> represented as a std::vector<int> (or so).

Are you familiar with arithmetic in finite fields? You will need to
look that up if you don't understand what Martin means with "schoolbook
quadratic polynomial multiplication .. modulo some minimal polynomial."

I don't have a reference handy right now. Wikipedia seems to
concentrate on characteristic 2 (specifically Rijndael's GF(8)). Feel
free to ask if you don't find any reference.


Cheers,
Burcin

[Martin Albrecht]

> Are you familiar with arithmetic in finite fields? You will need to
> look that up if you don't understand what Martin means with "schoolbook
> quadratic polynomial multiplication .. modulo some minimal polynomial."

Hi, sorry for my ignorance, I should have asked!

[Martin Albrecht]

On Sunday 21 Apr 2013, Siddharth Bhatia wrote:
> Thanks for the help. I am reading about finite field arithmetic. Any more
> references are definitely welcome.
>
> I installed gmp-5.1.1 but was not able to install lela earlier. I had to
> write ./configure --with-gmp-prefix= instead of ./configure --with-gmp= as
> mentioned in the manual. Studied for some time about gmp to check if there
> was an error there. So took some time there.
>
> I have one problem. When I'm trying sample code say with integers.h, I am
> just getting loads of errors on compiling. I just need to compile a normal
> c++ file, using g++ filename.cpp right?

Hey,

no you need to tell your compiler where to find the GMP + LELA headers and the
linker where to find the GMP and LELA library:

LELA_DIR="where you installed LELA + GMP etc."

g++ -I$LELA_DIR/include # where to find headers
-L$LELA_DIR/lib # where to find libraries
-lstdc++ -lm4ri -lgmp -llela -lgmpxx # what to link against
test.cpp -o test

[Bradford Hovinen]

Hi Siddarth,

There is a little script in LELA called lela-config which outputs the correct command-line options so that you can compile and link against the library, including all dependencies. Use it as follows:

g++ `lela-config --cflags --libs` <sources> -o <output>

Best regards,

Bradford Hovinen

2013/4/22 Martin Albrecht <martinr...@googlemail.com>

--
You received this message because you are subscribed to the Google Groups "LELA Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to lela-users+...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Martin Albrecht]

have you tried using lela-config as Bradford recommended?

On Monday 22 Apr 2013, Siddharth Bhatia wrote:
> Thanks a lot for the help you're providing. After installing m4ri and other
> libraries, I saw some gmp errors. I installed all packages related to gmp
> even though I had installed gmp properly earlier.
> Still during compilation I'm getting the following errors. Any suggestions
> as to how to overcome this problem?
>
>
> siddharth@siddharth:~$ g++ -L/usr/local/include/ -L/usr/local/lib -lstdc++
> -lgmp -lm4ri -llela -lgmpxx lela1.cpp
>
> /tmp/ccdIvocf.o: In function `__gmp_unary_minus::eval(__mpz_struct*,
> __mpz_struct const*)':
> lela1.cpp:(.text._ZN17__gmp_unary_minus4evalEP12__mpz_structPKS0_[__gmp_una
> ry_minus::eval(__mpz_struct*, __mpz_struct const*)]+0x1f): undefined
> reference to `__gmpz_neg'
> /tmp/ccdIvocf.o: In function `__gmp_binary_plus::eval(__mpz_struct*,
> __mpz_struct const*, __mpz_struct const*)':
> lela1.cpp:(.text._ZN17__gmp_binary_plus4evalEP12__mpz_structPKS0_S3_[__gmp_
> binary_plus::eval(__mpz_struct*, __mpz_struct const*, __mpz_struct
> const*)]+0x27): undefined reference to `__gmpz_add'
> /tmp/ccdIvocf.o: In function `__gmp_binary_minus::eval(__mpz_struct*,
> __mpz_struct const*, __mpz_struct const*)':
> lela1.cpp:(.text._ZN18__gmp_binary_minus4evalEP12__mpz_structPKS0_S3_[__gmp
> _binary_minus::eval(__mpz_struct*, __mpz_struct const*, __mpz_struct
> const*)]+0x27): undefined reference to `__gmpz_sub'
> /tmp/ccdIvocf.o: In function `__gmp_binary_multiplies::eval(__mpz_struct*,
> __mpz_struct const*, __mpz_struct const*)':
> lela1.cpp:(.text._ZN23__gmp_binary_multiplies4evalEP12__mpz_structPKS0_S3_[
> __gmp_binary_multiplies::eval(__mpz_struct*, __mpz_struct const*,
> __mpz_struct const*)]+0x27): undefined reference to `__gmpz_mul'
> /tmp/ccdIvocf.o: In function `__gmp_binary_divides::eval(__mpz_struct*,
> __mpz_struct const*, __mpz_struct const*)':
> lela1.cpp:(.text._ZN20__gmp_binary_divides4evalEP12__mpz_structPKS0_S3_[__g
> mp_binary_divides::eval(__mpz_struct*, __mpz_struct const*, __mpz_struct
> const*)]+0x27): undefined reference to `__gmpz_tdiv_q'
> /tmp/ccdIvocf.o: In function `__gmp_binary_modulus::eval(__mpz_struct*,
> __mpz_struct const*, __mpz_struct const*)':
> lela1.cpp:(.text._ZN20__gmp_binary_modulus4evalEP12__mpz_structPKS0_S3_[__g
> mp_binary_modulus::eval(__mpz_struct*, __mpz_struct const*, __mpz_struct
> const*)]+0x27): undefined reference to `__gmpz_tdiv_r'
> /tmp/ccdIvocf.o: In function `__gmp_binary_equal::eval(__mpz_struct const*,
> __mpz_struct const*)':
> lela1.cpp:(.text._ZN18__gmp_binary_equal4evalEPK12__mpz_structS2_[__gmp_bin
> ary_equal::eval(__mpz_struct const*, __mpz_struct const*)]+0x1f): undefined
> reference to `__gmpz_cmp' /tmp/ccdIvocf.o: In function
> `__gmp_binary_equal::eval(__mpz_struct const*, long)':
> lela1.cpp:(.text._ZN18__gmp_binary_equal4evalEPK12__mpz_structl[__gmp_binar
> y_equal::eval(__mpz_struct const*, long)]+0x1f): undefined reference to
> `__gmpz_cmp_si'
> /tmp/ccdIvocf.o: In function `__gmp_expr<__mpz_struct [1], __mpz_struct
> [1]>::__gmp_expr()':
> lela1.cpp:(.text._ZN10__gmp_exprIA1_12__mpz_structS1_EC2Ev[_ZN10__gmp_exprI
> A1_12__mpz_structS1_EC5Ev]+0x14): undefined reference to `__gmpz_init'
> /tmp/ccdIvocf.o: In function `__gmp_expr<__mpz_struct [1], __mpz_struct
> [1]>::__gmp_expr(int)':
> lela1.cpp:(.text._ZN10__gmp_exprIA1_12__mpz_structS1_EC2Ei[_ZN10__gmp_exprI
> A1_12__mpz_structS1_EC5Ei]+0x20): undefined reference to
> `__gmpz_init_set_si'
> /tmp/ccdIvocf.o: In function `__gmp_expr<__mpz_struct [1], __mpz_struct
> [1]>::~__gmp_expr()':
> lela1.cpp:(.text._ZN10__gmp_exprIA1_12__mpz_structS1_ED2Ev[_ZN10__gmp_exprI
> A1_12__mpz_structS1_ED5Ev]+0x14): undefined reference to `__gmpz_clear'
> /tmp/ccdIvocf.o: In function `__gmp_expr<__mpz_struct [1], __mpz_struct
> [1]>::operator=(__gmp_expr<__mpz_struct [1], __mpz_struct [1]> const&)':
> lela1.cpp:(.text._ZN10__gmp_exprIA1_12__mpz_structS1_EaSERKS2_[__gmp_expr<_
> _mpz_struct [1], __mpz_struct [1]>::operator=(__gmp_expr<__mpz_struct [1],
> __mpz_struct [1]> const&)]+0x1f): undefined reference to `__gmpz_set'
> /tmp/ccdIvocf.o: In function `__gmp_expr<__mpz_struct [1], __mpz_struct
> [1]>::operator=(int)':
> lela1.cpp:(.text._ZN10__gmp_exprIA1_12__mpz_structS1_EaSEi[__gmp_expr<__mpz
> _struct [1], __mpz_struct [1]>::operator=(int)]+0x20): undefined reference
> to `__gmpz_set_si'
> /tmp/ccdIvocf.o: In function `__gmp_expr<__mpz_struct [1], __mpz_struct
> [1]>::get_d() const':
> lela1.cpp:(.text._ZNK10__gmp_exprIA1_12__mpz_structS1_E5get_dEv[__gmp_expr<
> __mpz_struct [1], __mpz_struct [1]>::get_d() const]+0x14): undefined
> reference to `__gmpz_get_d'
> /tmp/ccdIvocf.o: In function `std::basic_ostream<char,
> std::char_traits<char> >& operator<< <__mpz_struct
> [1]>(std::basic_ostream<char, std::char_traits<char> >&,
> __gmp_expr<__mpz_struct [1], __mpz_struct [1]> const&)':
> lela1.cpp:(.text._ZlsIA1_12__mpz_structERSoS2_RK10__gmp_exprIT_S4_E[std::ba
> sic_ostream<char, std::char_traits<char> >& operator<< <__mpz_struct
> [1]>(std::basic_ostream<char, std::char_traits<char> >&,
> __gmp_expr<__mpz_struct [1], __mpz_struct [1]> const&)]+0x2a): undefined
> reference to `operator<<(std::basic_ostream<char, std::char_traits<char>
>
> >&, __mpz_struct const*)'
>
> /tmp/ccdIvocf.o: In function `std::basic_istream<char,
> std::char_traits<char> >& operator>><__mpz_struct
> [1]>(std::basic_istream<char, std::char_traits<char> >&,
> __gmp_expr<__mpz_struct [1], __mpz_struct [1]>&)':
> lela1.cpp:(.text._ZrsIA1_12__mpz_structERSiS2_R10__gmp_exprIT_S4_E[std::bas
> ic_istream<char, std::char_traits<char> >& operator>><__mpz_struct
> [1]>(std::basic_istream<char, std::char_traits<char> >&,
> __gmp_expr<__mpz_struct [1], __mpz_struct [1]>&)]+0x2a): undefined
> reference to `operator>>(std::basic_istream<char, std::char_traits<char>
>
> >&, __mpz_struct*)'
>
> /tmp/ccdIvocf.o: In function `__gmp_expr<__mpz_struct [1], __mpz_struct
> [1]>::__gmp_expr<__mpz_struct [1],
> __gmp_binary_expr<__gmp_expr<__mpz_struct [1], __mpz_struct [1]>,
> __gmp_expr<__mpz_struct [1], __mpz_struct [1]>, __gmp_binary_modulus>
>
> >(__gmp_expr<__mpz_struct [1], __gmp_binary_expr<__gmp_expr<__mpz_struct
>
> [1], __mpz_struct [1]>, __gmp_expr<__mpz_struct [1], __mpz_struct [1]>,
> __gmp_binary_modulus> > const&)':
> lela1.cpp:(.text._ZN10__gmp_exprIA1_12__mpz_structS1_EC2IS1_17__gmp_binary_
>
exprIS2_S2_20__gmp_binary_modulusEEERKS_IT_T0_E[_ZN10__gmp_exprIA1_12__mpz_
> structS1_EC5IS1_17__gmp_binary_exprIS2_S2_20__gmp_binary_modulusEEERKS_IT_T
> 0_E]+0x18): undefined reference to `__gmpz_init'
> /tmp/ccdIvocf.o: In function `__gmp_expr<__mpz_struct [1], __mpz_struct
> [1]>::__gmp_expr<__mpz_struct [1],
> __gmp_binary_expr<__gmp_expr<__mpz_struct [1], __mpz_struct [1]>,
> __gmp_expr<__mpz_struct [1], __mpz_struct [1]>, __gmp_binary_multiplies>
>
> >(__gmp_expr<__mpz_struct [1], __gmp_binary_expr<__gmp_expr<__mpz_struct
>
> [1], __mpz_struct [1]>, __gmp_expr<__mpz_struct [1], __mpz_struct [1]>,
> __gmp_binary_multiplies> > const&)':
> lela1.cpp:(.text._ZN10__gmp_exprIA1_12__mpz_structS1_EC2IS1_17__gmp_binary_
> exprIS2_S2_23__gmp_binary_multipliesEEERKS_IT_T0_E[_ZN10__gmp_exprIA1_12__m
> pz_structS1_EC5IS1_17__gmp_binary_exprIS2_S2_23__gmp_binary_multipliesEEERK
> S_IT_T0_E]+0x18): undefined reference to `__gmpz_init'
> collect2: ld returned 1 exit status
>
>
> Regards
> Siddharth Bhatia
> BITS Pilani

[Burcin Erocal]

Hi,

perhaps you are picking up the headers for the wrong GMP version.

> > On Monday 22 Apr 2013, Siddharth Bhatia wrote:

<snip>

> > > siddharth@siddharth:~$ g++ -L/usr/local/include/ -L/usr/local/lib
> > -lstdc++
> > > -lgmp -lm4ri -llela -lgmpxx lela1.cpp

You probably need

-I/usr/local/include

instead of -L/usr/local/include above.


If you cannot get any further, feel free to drop by IRC and ping me to
debug this online.

Cheers,
Burcin

P.S. lmonade is supposed to solve this problem exactly. Unfortunately,
we don't support LELA just yet. I never got to polish previous attempts
by students in Kaiserslautern and include it in lmonade.