Opened 10 years ago
Closed 7 years ago
#12117 closed enhancement (fixed)
Bugfixes and improvements to Aurifeuillian factorization
Reported by:  roed  Owned by:  AlexGhitza 

Priority:  major  Milestone:  sage6.2 
Component:  factorization  Keywords:  
Cc:  jpflori  Merged in:  
Authors:  David Roe  Reviewers:  Ralf Stephan, Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  e4307b3 (Commits, GitHub, GitLab)  Commit:  e4307b38942719c161de03e161b06f29f9ff5fed 
Dependencies:  #12116, #12109  Stopgaps: 
Description
sage: from sage.rings.factorint import factor_aurifeuillian as fa sage: fa(2^6006 + 1) [...]
This should produce a splitting, but instead it just returns a singleton. The problem is that there's rounding error because of the fixed precision of 300 in aurifeuillian.
This patch also updates this factorization function to allow for a greater variety of bases.
Attachments (1)
Change History (13)
comment:1 Changed 10 years ago by
 Dependencies changed from #12116 to #12116, #12109
 Status changed from new to needs_review
comment:2 Changed 10 years ago by
 Component changed from basic arithmetic to factorization
comment:3 Changed 8 years ago by
 Cc jpflori added
comment:4 Changed 8 years ago by
comment:5 Changed 8 years ago by
Fixed some problems pointed out by Simon.
comment:6 Changed 8 years ago by
To try to get patchbot to apply a different patch for 12116:
Apply 12117.patch
Changed 8 years ago by
comment:7 Changed 8 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:8 Changed 7 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:9 Changed 7 years ago by
 Branch set to u/rws/ticket/12117
 Modified changed from 01/30/14 21:20:52 to 01/30/14 21:20:52
comment:10 Changed 7 years ago by
 Commit set to c8770e15df28dad32768a09f4319cf1ccdb5695f
 Reviewers set to Ralf Stephan
 Status changed from needs_review to positive_review
Fine as far as I can see. I tested rings/ long and compared manually a few values from the Cunningham tables.
New commits:
c8770e1  Trac #12117: Update aurifeuillian factorization in sage.rings.factorint

comment:11 Changed 7 years ago by
 Branch changed from u/rws/ticket/12117 to u/tscrim/ticket/12117
 Commit changed from c8770e15df28dad32768a09f4319cf1ccdb5695f to e4307b38942719c161de03e161b06f29f9ff5fed
 Reviewers changed from Ralf Stephan to Ralf Stephan, Travis Scrimshaw
comment:12 Changed 7 years ago by
 Branch changed from u/tscrim/ticket/12117 to e4307b38942719c161de03e161b06f29f9ff5fed
 Resolution set to fixed
 Status changed from positive_review to closed
Note: See
TracTickets for help on using
tickets.
Rebased against 5.8.beta0.