mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2015-01-11, 12:51   #1
mickfrancis
 
Apr 2014
Marlow, UK

23·7 Posts
Default Cyclotomic Polynomial Factoring methods

Could anyone tell me whether ECM renders Cyclotomic Polynomial Factoring methods obsolete (other than p-1, as it is a constant factor faster than ECM if it succeeds, I believe)?

Or, is there a significant possibility that for some k and N=pq, PHI_k(p) might be smooth where ECM finds no results?

Are there any industrial-strength implementations of Cyclotomic Polynomial Factoring for values of k where the degree of PHI_k(p) > 2?

(Sorry if this is a stupid question - I'm just enjoying learning about these methods at the moment...)
mickfrancis is offline   Reply With Quote
Old 2015-01-11, 14:40   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by mickfrancis View Post
Could anyone tell me whether ECM renders Cyclotomic Polynomial Factoring methods obsolete (other than p-1, as it is a constant factor faster than ECM if it succeeds, I believe)?
They were obsolete the moment Bach & Shallit wrote their paper.

Last fiddled with by R.D. Silverman on 2015-01-11 at 14:40
R.D. Silverman is offline   Reply With Quote
Old 2015-01-11, 18:31   #3
mickfrancis
 
Apr 2014
Marlow, UK

23×7 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
They were obsolete the moment Bach & Shallit wrote their paper.
Bit of a shame for Bach & Shallit - still, an interesting paper (to me, at least!)
mickfrancis is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Polynomials defining the same field as cyclotomic polynomial order 5 carpetpool Abstract Algebra & Algebraic Number Theory 0 2017-04-19 20:33
Polynomial whose coefficients add up to n defining Cyclotomic field K. carpetpool Miscellaneous Math 3 2017-04-07 02:15
Cyclotomic primes (degree>=5) Batalov And now for something completely different 0 2016-06-21 21:02
Can discrete logarithms / factoring be done in P (i.e., deterministic polynomial time)? Raman Factoring 1 2016-05-23 13:44
Cyclotomic Phi plandon Math 22 2009-07-29 18:59

All times are UTC. The time now is 17:39.

Fri Apr 16 17:39:43 UTC 2021 up 8 days, 12:20, 0 users, load averages: 3.18, 3.36, 3.32

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.