Project

General

Profile

Bug #1233

factor SEGV -- too large characteristic

Added by John Abbott over 5 years ago. Updated about 1 year ago.

Status:
Resolved
Priority:
High
Assignee:
John Abbott
Category:
Maths Bugs
Target version:
CoCoALib-0.99880
Start date:
08 Nov 2018
Due date:
% Done:

60%

Estimated time:
Spent time:
1.70 h

Description

factor can cause a SEGV if the characteristic is NextProbPrime(2^31).

p := NextProbPrime(2^31);
use ZZ/(p)[x];
factor(x^2+1); --> SEGV

History

#1 Updated by John Abbott over 5 years ago

Obviously I discovered the bug while demoing CoCoA-5 :-/

Ange would like to be able to factorize (univariate polys) over large characteristic.

#2 Updated by John Abbott over 5 years ago

  • Status changed from New to Resolved
  • Assignee set to John Abbott
  • % Done changed from 0 to 60

I have found two bugs related to the old code in the factorizer which uses int (for speed?) rather than long.
I have patched the bugs, but cannot yet check in until I fix my VPN settings.

This does prompt some questions:
  • make two copies of the old factorizer code (one based on int, and the other based on long) and see if there is a significant speed difference
  • if there is a significant speed difference then both versions must be incorporated and a suitable dispatch function added.
  • there should also be an impl for "unlimited" characteristic (which is to be used only when native integers cannot cope)

But where to find the time to do all this?

#3 Updated by John Abbott about 5 years ago

  • Target version changed from CoCoALib-0.99650 November 2019 to CoCoALib-0.99700

#4 Updated by John Abbott over 4 years ago

This now gives error rather than SEGV -- so that is an improvement!

#5 Updated by John Abbott over 4 years ago

  • Target version changed from CoCoALib-0.99700 to CoCoALib-0.99800

#6 Updated by John Abbott about 4 years ago

  • Target version changed from CoCoALib-0.99800 to CoCoALib-0.99850

#7 Updated by John Abbott over 3 years ago

  • Subject changed from factor SEGV to factor SEGV -- too large characteristic

#8 Updated by John Abbott over 3 years ago

Revised example (now that we're mostly 64 bit)

p := NextProbPrime(2^63);
use ZZ/(p)[x];
factor(x^2+1); --> SEGV

I have just tested the example: it no longer gives SEGV, but does give a CoCoA error (cannot convert).

#9 Updated by John Abbott about 1 year ago

  • Target version changed from CoCoALib-0.99850 to CoCoALib-0.99880

I have just tried:

p := NextPrime(2^31);
use ZZ/(p)[x];
factor(x^2+1);  --> almost instant
p := NextPrime(p);
use ZZ/(p)[x];
factor(x^2+1);   --> SLOW!  stopped it after several minutes.

Not sure if it can really be made any faster. It would be nice if the code were interruptible.
Current state is "tolerable", but the issue is not really resolved. Postponing.

Also available in: Atom PDF