<p>See my paper with Eric Bach, "Factoring with cyclotomic polynomials", where we show that if the cyclotomic polynomial $\Phi_k(p)$ is $B$-smooth for any $p$ dividing $N$, then we can factor $N$ in time polynomial in $\log N$ and $k$ and $B$.  In particular this gives a $(p+1)$-method (see the earlier work of Williams) and $(p^2+1)$ method.</p>

<p><a href="http://www.ams.org/journals/mcom/1989-52-185/S0025-5718-1989-0947467-1/S0025-5718-1989-0947467-1.pdf">http://www.ams.org/journals/mcom/1989-52-185/S0025-5718-1989-0947467-1/S0025-5718-1989-0947467-1.pdf</a></p>

CC BY-SA 3.0
2016-07-03T18:46:34.177Z
2016-07-03T18:46:34.177Z
Jeffrey Shallit
<p>I have came across a lot of factorization methods and most of them seem to assume smoothness of some numbers.</p>

<p>For example</p>

<ol>
<li>When $p-1$ is smooth</li>
<li>When $|E(\mathbb{F}_p)|$ is smooth. (Elliptic curve factorization)</li>
<li>Smoothness of prime ideals in Number field sieves.</li>
</ol>

<p>I want to know whether any other notions are known to be equivalent to factoring like smoothness of $p+1$ or $p^2+1$  ?</p>

<nt.number-theory><factoring><cryptographic-attack>
Factoring assuming smoothness of some numbers
xyz
# Factoring assuming smoothness of some numbers

(Asked by: username_0 on 2016-07-03)

I have came across a lot of factorization methods and most of them seem to assume smoothness of some numbers.

For example

1. When $p-1$ is smooth
2. When $|E(\mathbb{F}\_p)|$ is smooth. (Elliptic curve factorization)
3. Smoothness of prime ideals in Number field sieves.

I want to know whether any other notions are known to be equivalent to factoring like smoothness of $p+1$ or $p^2+1$ ?

**Tags:** nt.number-theory, factoring, cryptographic-attack

---

## 1 answers

### Answer by username_1 on 2016-07-03. Score: 9 | Accepted answer

See my paper with Eric Bach, "Factoring with cyclotomic polynomials", where we show that if the cyclotomic polynomial $\Phi\_k(p)$ is $B$-smooth for any $p$ dividing $N$, then we can factor $N$ in time polynomial in $\log N$ and $k$ and $B$. In particular this gives a $(p+1)$-method (see the earlier work of Williams) and $(p^2+1)$ method.

<http://www.ams.org/journals/mcom/1989-52-185/S0025-5718-1989-0947467-1/S0025-5718-1989-0947467-1.pdf>


---

