## 160 Reputation

6 years, 142 days

## Bug in modp1(('Rem')(...))...

Maple 2020

Hi there.

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

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

## Fast Extended Euclidean Algorithm in Har...

Maple

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

## modp1 Resultant...

Hi there,

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

Thank you.

## modpol analogue...

Maple 2020

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

## Output field in Maple...

Maple

Hi there.

Is it possible to erase previous value of output field and to put new value into it?

For example, I want instead this:

to get something like this:

after first iteration

after fifth iteration

and after tenth iteration

How I can do it?

 1 2 3 4 Page 3 of 4
﻿