MinPolyQuot: runs out of primes
MinPolyQuot on a slightly big example, and it ran out of primes.
This is surely a problem with all modular methods; we must find a good solution.
#1 Updated by John Abbott about 1 year ago
Here is an example input which triggers the problem (after about 12 mins' CPU time)
use P::=QQ[x,y,z]; DEG := 6; S := support((1+sum(indets(P)))^DEG); define RndPoly(S) return sum([random(-99,99)*t | t in S]); enddefine; -- RndPoly L := [RndPoly(S) | i in 1..3]; I := ideal(L); IsZeroDim(I); QB := QuotientBasis(I); f := RndPoly(QB); StartTime := CpuTime(); mu := MinPolyQuot(f,I,x); EndTime := CpuTime(); println "MinPoly time: ", DecimalStr(EndTime-StartTime);
#6 Updated by Anna Maria Bigatti about 1 year ago
John Abbott wrote:
I have just tried running the example from the comment above but with verbosity level 80.
It prints out each prime used and also a polynomial from
It would be useful to have the poly print out only at a slightly higher level of verbosity.
raised to level 85
#8 Updated by Anna Maria Bigatti about 1 year ago
John Abbott wrote:
The problem is not yet fixed (but I did have to try "hard" to make a big enough example).
all primes from 46000 down to 2 were not enough!?!?!
What monster example have you done?
The code should switch from "fast" finite fields to "slow" ones in case of need.
I suppose I must look into it. :-/
That would make lots of code very very tedious....
Have you tried using "MinPolyDefQuot" (which is not modular)?
#9 Updated by John Abbott about 1 year ago
- Status changed from In Progress to Resolved
- % Done changed from 50 to 80
I think I have fixed the code: the only real change needed was to use
NewZZmod instead of
This allows the use of primes above 46000 (or whatever the previous limit was). For small examples there is no measurable speed penalty.
NewZZmod tries to be clever: it will actually call
NewRingFp if possible.
I have made it clearer in the documentation for
RingFp that one should normally use
I'll let Anna check the code quickly, and move it to "feedback" if she is convinced.