5
$\begingroup$

The Carmichael Numbers can be factorized in polynomial time.

Are weak fermat pseudoprimes (w.r.t. a given base) easy to factorize as well?

What are some large/broad classes of numbers that are easy to factorize (i.e. in polynomial time). This part is pretty broad, so i would be thankful if someone can provide some examples of these classes and more importantly a few good up-to date sources, that studies/lists the classes of numbers and their factorization difficulty ?

$\endgroup$
  • 2
    $\begingroup$ Thanks to the AKS primality test, we now know that numbers which are "secretly" prime can be factored in polynomial time. Also, Shor's algorithm factors every integer in polynomial time, you just need a big quantum computer. So, technically, every integer is easy to factor (with the right equipment). Do you mean using a classical computer? $\endgroup$ – Pace Nielsen Sep 7 '16 at 18:16
  • $\begingroup$ On the other hand, it is easy to factor numbers which are the product of two primes which are very close together. (You might consider this not a "natural" class of numbers, but it does arise when trying to keep public-key cryptography more secure.) $\endgroup$ – Pace Nielsen Sep 7 '16 at 18:18
  • $\begingroup$ Much thanks. I am aware of Shor's Algorithm. So I should have mentioned using classical computers. The criteria that the numbers are too close would make their practial factorization easier is a very useful tool, but as you pointed out i am looking for some class with a definite criteria. For example Carmichael Numbers or case of weak pseudoprimes to a given base? $\endgroup$ – TheoryQuest1 Sep 7 '16 at 18:28
  • 2
    $\begingroup$ What about the primes? $\endgroup$ – joro Sep 8 '16 at 4:47
8
$\begingroup$

Six classes of "lucky numbers", that can be factorized easily, are discussed on page 107 and following of Integer Factoring by Arjen Lenstra (2000). These include: trial division by a small prime (very effective, since 88% of all positive integers have a factor $< 100$, and almost 92% have a factor $< 1000$), Pollard's rho method and the elliptic curve method (if some random number close to some prime factor of $n$ is "smooth", in the sense that all its prime factors are small), Fermat's method (for numbers that have two large prime factors close to each other), congruence of squares (for numbers $n$ for which there exist $x$ and $y$ such that $x^2-y^2$ is a multiple of $n$).

$\endgroup$
  • $\begingroup$ Thanks for the detailed answer. If I am correct given a base for which a number is a fermat pseudoprime its also always easy to factorize the given number. Please correct me if I am wrong ? $\endgroup$ – TheoryQuest1 Sep 8 '16 at 5:55
3
$\begingroup$

Here is a large class of numbers that can be factored in polynomial time: products of a smooth number and large prime. More precisely, a number less than $x$ whose second largest prime factor is less than $\exp(O((\log \log x)^2/\log \log \log x))$ can be factored in polynomial time. There are about $$x(\log\log x)^2/(\log x \log\log\log x)$$ such numbers, so this is quite a large class. You can read more in Granville's survey Smooth numbers: computational number theory and beyond.

$\endgroup$
3
$\begingroup$

Here are some classes of numbers that can be fully factored efficiently with high probability.

Let $p_i$ be primes such that $2 p_i + 1$ are also primes and $q$ arbitrary prime.

Let $n'=\prod_{i=1}^n (2p_i+1)$ and $n''=\prod_{i=1}^n p_i$.

Let $N= q n' n ''$. Then $N$ can be factored completely efficiently with high probability.

We have $\phi(n')=2^n n''$. Knowing a multiple of the totient function factors the number with high probability (essentially always). For reference see Wong's answer here: https://math.stackexchange.com/questions/191896/does-knowing-the-totient-of-a-number-help-factoring-it

By this argument we factor $n'$ and from $p=2p_i+1$ we get $p_i$ which is prime.This leaves only $q$.

By similar argument for sigma, we can replace $2p_i+1$ by $2 p_i -1$.


Added 2016-12-01

A New Special-Purpose Factorization Algorithm Qi Cheng ∗ In this paper, a new factorization algorithm is presented, which finds a prime factor $p$ of an integer $n$ in time $(D\log{n})^{O(1)} $, if $4p - 1 = Db^2$ where $D$ and $b$ are integers. Hence this algorithm will factor a number efficiently, if it has a prime factor p such that $4p - 1$ is a product of a small integer and a square.

$\endgroup$
2
$\begingroup$

Pollard's $p-1$ method will likely find $p$ quickly if $p-1$ is a least common multiple of positive integers, all of which are small. (To put it another way, $p-1$ is a product of small primes, none of which is repeated too many times.)

There are analogous methods that target $p+1$ or any other product of cyclotomic polynomials in $p$; the key is to compute in a different group modulo $p$. Computation in $F_{p^{2}}^{\times}$, for example, can be accomplished using sequences satisying second-order linear recurrences, using $2 \times 2$ matrices, or other methods.

Also, if there is a small (positive integral) multiplier $c$ such that $n$ has a divisor $d$ such that $cd$ and $\frac{n}{d}$ are very close, a variant of Fermat's method with multipliers will factor $n$ by finding $cn = (\frac{cd+\frac{n}{d}}{2})^{2}-(\frac{cd-\frac{n}{d}}{2})^{2}$. (This assumes that $c$ will not interfere with the calculation of $\gcd (cd,n)$. But if $c$ is small, then trial division up to $c$, among other methods, can rule out $n$ having such small prime factors.)

$\endgroup$
  • $\begingroup$ Do you really need the small primes to not be repeated too many times? Prime $q$ can't be with exponent greater than $\log_q{p-1}$. It does hurt to use higher exponent. $\endgroup$ – joro Sep 8 '16 at 5:35
  • $\begingroup$ I thought about that, and realized why the $p-1$ method proceeds that way. This is an approximate optimization designed to find $p$ as quickly as possible. It is approximately true that larger prime-powers are less likely to divide $p-1$ than smaller ones (the exact statement would compare their $\phi$-values, recognizing Dirichlet's Theorem), so the least common multiple in the exponent puts a smaller prime-power in before it puts a larger one. (It doesn't sound hugely difficult to rework this to sort prime-powers by their $\phi$-values, though.) $\endgroup$ – DavidLHarden Sep 8 '16 at 7:18

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.