Hi all,

There is issue with modp1(('Embed')(...)) function.

Please look at the file:

bug_embed.mw

As you can see in lines 1, 3, 5 Embed function in combining with Constant cutting several digits from argument.

Thank you.

Hi there.

It seems like a bug in modp1(('Rem')(...)) with large polynomials with large coefficients.

Please look at the file:

bug_rem.mw

It needs the file polys.m there:

https://dropmefiles.com/9fATR

File polys.m too big for this forum so I used dropmefiles.

Polys.m contain two polynomials x and f_t with large degrees: degree(f_t) = m = 50021, degree(x) = 2*m - 2 = 100040 and large coefficients up to 2^N, where N = ceil(m / 2)+2 = 25013.

I just compute rem(x,f_t) mod 2^N.

As you can see in the first part of doc bug_rem.mw I decreased coefficients of polynomials by additional mod 2^N (with Embed function), where N = floor(N / 2) = 12506. WIth these decreased polynomials and decreased N modp1(('Rem')(...)) function works well and use maximum about 2.5 Gb of RAM.

But in the second part of doc bug_rem.mw with original polynomials and N = 25013 modp1(('Rem')(...)) use maximum about 3.5 Gb of RAM and crash with error:

Error, Maple was unable to allocate enough memory to complete this computation.  Please see ?alloc
 

This is strange and looks like a bug considering that the test server has 48 Gb of RAM.

Is it a bug or modp1(('Rem')(...)) just need more than 48 Gb of RAM?

How many RAM it needs for this computation?

Thank you

Hi there,

Could you help me with Harley's norm computation algorithm that is based on the Fast Extended Euclidean Algorithm that was suggested by Harley in an email to NMBRTHRY list in 2002 and that described in Vercauteren's thesis pp 87-90:

https://pdfs.semanticscholar.org/c945/c98267db064b272c87a885fc5eeb764b0b2d.pdf

My implementation working correctly and fast for low degree polynomials without modulo and for high degree polynomials with modulo M, where M is a prime number greater than 2^N. But all I need - it's a resultant modulo 2^N (or 2^(Nc) due to Vercauteren's Remark 3.10.3) of two large polynomials. So I should include in routine mod 2^N (or mod 2^(Nc)...) instructions to avoid exponential coefficients' growing. But since the 2^N is not prime it's a problem - polynomials contain even coefficients and this leads to some even denominators - and for example multiplicative inverse 1/2 mod 2^N doesn't exist. Please tell me how to solve this problem?

How to adapt XGCD routine for correct mod 2^N calculation of resultant (norm)?

Thank you.

mod prime version of XGCD:

XGCD.mw

Hi there,

What is the algorithm implemented in Maple's function modp1(('Resultant')(...)?

Thank you.

Hi there.

I need to calculate multiplcations of huge polynoms with reducing in GF(2^m) with m>1000.

For example, modpol(a*a,f_t,t,2^N) with N=4007, degree(a)=8008 and degree(f_t)=8009.

Standard modpol calculates this in 4-5 sec on my computer.

Maybe there is an easy way to speed up this calculation?

Thank you.

ex.mw

nn.txt