<p>I'll address this form of the question suggested in the comments:</p>
<blockquote>
<p>Would an algorithm that factors numbers of the form <span class="math-container">$N = (3^n+x)(2^m+y)$</span> be useful, where <span class="math-container">$x$</span> and <span class="math-container">$y$</span> can have a value from <span class="math-container">$1$</span> to <span class="math-container">$2^{250}$</span> and <span class="math-container">$n, m$</span> are unrestricted?</p>
</blockquote>
<p>First, how fast is the algorithm? Trial division takes time <span class="math-container">$O(\sqrt N)$</span> which is <span class="math-container">$\exp(O(\log N))$</span> and the number field sieve takes time <span class="math-container">$\exp(O((\log N)^{1/3}(\log\log N)^{2/3}))$</span>. Running through each number of the above form takes time <span class="math-container">$O(\log^2 N)$</span> which is <span class="math-container">$\exp(O(\log\log N))$</span>. So just being of that form gives you a huge speedup in computational complexity.</p>
<p>But if the algorithm has novel insights, perhaps it could be interesting to study.</p>
<p>On a practical level, if it were fast enough it could be useful for some cases. Every number with up to 75 digits is of this form, and most interesting numbers (in terms of hardness of factorization) up to 150 digits are of this form. So it could be a useful replacement for SIQS or NFS for small numbers, and could be used as a subroutine for factoring larger numbers. If it were instant that would lead to a somewhat faster number field sieve for moderately-sized numbers.</p>
<p>If you do have a fast algorithm for factoring such numbers, perhaps you could factor N = 3483199037737426090084842665153878458506048638439016353714695861794863252354872716815648422167549634981170589561810105410226481425840126372542074168393 as an example (151 digits) which is of the form above.</p>

CC BY-SA 4.0
2023-07-03T18:04:40.457Z
2023-07-03T18:04:40.457Z
Charles
<p>Based on a response I received in another post, I would like to ask this question.</p>
<p>Are there semiprimes that are not very interesting in terms of research and are not worth factoring?</p>
<p>Are only the RSA ones interesting?</p>
<p>Let's take this as an example, it is not an RSA but no known algorithm is able to factor it in a short time.</p>
<p>3149529599058497427029650543012108677994872225908863841683093373209394393926404717536899439720744342512950369958868474662291266402859672163</p>
<p>The question is: if someone can find an algorithm that can factor this semiprime, wouldn't it be interesting just because it's not an RSA?</p>
<p>Thanks for the replies</p>

CC BY-SA 4.0
2023-05-27T15:35:59.453Z
If someone can factor just this semiprime, it's worthless. Factoring any single number is worthless. If, on the other hand, someone finds an algorithm that can efficiently factorize a nontrivial *class* of semiprimes that are not too rare, and cannot be factored efficiently with previously known algorithms, this could be interesting.
Emil Jeřábek
CC BY-SA 4.0
2023-05-27T16:25:59.767Z
It's not just one number. Can you specify non-trivial class? (((3^1401)+2^50)+1562346) * (((2^2303-1)+2^50)+1607418)  Can the product of these two prime factors be considered a trivial class?
claudio G
CC BY-SA 4.0
2023-05-27T17:27:34.180Z
Again: a single number is always a trivial class. At the very least it should be an infinite family of numbers.
Emil Jeřábek
CC BY-SA 4.0
2023-05-27T18:04:09.590Z
I correct the answer. (3^n+x)*(2^m+y) where x and y can have a value from 1 to 2^250 and n, m, can be very far apart. Do you mean this by class??
claudio G
CC BY-SA 4.0
2023-05-27T18:55:25.280Z
That kind of things, yes.
Emil Jeřábek
CC BY-SA 4.0
2023-07-04T23:34:05.477Z
per Chales Non riesco a risponderti perchè non ho abbastanza crediti perciò ti rispondo come ospite. Il numero che hai postato non è un semiprimo perchè è divisibile 118067861. Ti invito a vedere questi video nei quali mostro come funziona il mio algoritmo e dove c'è allegato il programma in python. Il programma non riporta il codice che individua la chiave di fattorizzazione ma contiene solo la chiave per fattorizzare quel tipo di semiprimi. Questo perchè al momento non voglio rivelare questo codice. https://youtu.be/gjED9D4gkfI https://youtu.be/J-XxkA2WhXk https://youtu.be/hfuTv-Y4uSw se lo
Claudio G.
<ds.algorithms><cr.crypto-security><factoring><primes><process-algebra>
help me understand what semiprime factorizations are worth
claudio G
# help me understand what semiprime factorizations are worth

(Asked by: username_0 on 2023-05-27)

Based on a response I received in another post, I would like to ask this question.

Are there semiprimes that are not very interesting in terms of research and are not worth factoring?

Are only the RSA ones interesting?

Let's take this as an example, it is not an RSA but no known algorithm is able to factor it in a short time.

3149529599058497427029650543012108677994872225908863841683093373209394393926404717536899439720744342512950369958868474662291266402859672163

The question is: if someone can find an algorithm that can factor this semiprime, wouldn't it be interesting just because it's not an RSA?

Thanks for the replies

**Tags:** ds.algorithms, cr.crypto-security, factoring, primes, process-algebra
> **Comments:**
> **username_1**: If someone can factor just this semiprime, it's worthless. Factoring any single number is worthless. If, on the other hand, someone finds an algorithm that can efficiently factorize a nontrivial *class* of semiprimes that are not too rare, and cannot be factored efficiently with previously known algorithms, this could be interesting.  
> **username_0**: It's not just one number. Can you specify non-trivial class? (((3^1401)+2^50)+1562346) * (((2^2303-1)+2^50)+1607418)  Can the product of these two prime factors be considered a trivial class?  
> **username_1**: Again: a single number is always a trivial class. At the very least it should be an infinite family of numbers.  
> **username_0**: I correct the answer. (3^n+x)*(2^m+y) where x and y can have a value from 1 to 2^250 and n, m, can be very far apart. Do you mean this by class??  
> **username_1**: That kind of things, yes.  
> **username_2**: per Chales Non riesco a risponderti perchè non ho abbastanza crediti perciò ti rispondo come ospite. Il numero che hai postato non è un semiprimo perchè è divisibile 118067861. Ti invito a vedere questi video nei quali mostro come funziona il mio algoritmo e dove c'è allegato il programma in python. Il programma non riporta il codice che individua la chiave di fattorizzazione ma contiene solo la chiave per fattorizzare quel tipo di semiprimi. Questo perchè al momento non voglio rivelare questo codice. https://youtu.be/gjED9D4gkfI https://youtu.be/J-XxkA2WhXk https://youtu.be/hfuTv-Y4uSw se lo  

---

## 1 answers

### Answer by username_3 on 2023-07-03. Score: 0

I'll address this form of the question suggested in the comments:

> Would an algorithm that factors numbers of the form $N = (3^n+x)(2^m+y)$ be useful, where $x$ and $y$ can have a value from $1$ to $2^{250}$ and $n, m$ are unrestricted?

First, how fast is the algorithm? Trial division takes time $O(\sqrt N)$ which is $\exp(O(\log N))$ and the number field sieve takes time $\exp(O((\log N)^{1/3}(\log\log N)^{2/3}))$. Running through each number of the above form takes time $O(\log^2 N)$ which is $\exp(O(\log\log N))$. So just being of that form gives you a huge speedup in computational complexity.

But if the algorithm has novel insights, perhaps it could be interesting to study.

On a practical level, if it were fast enough it could be useful for some cases. Every number with up to 75 digits is of this form, and most interesting numbers (in terms of hardness of factorization) up to 150 digits are of this form. So it could be a useful replacement for SIQS or NFS for small numbers, and could be used as a subroutine for factoring larger numbers. If it were instant that would lead to a somewhat faster number field sieve for moderately-sized numbers.

If you do have a fast algorithm for factoring such numbers, perhaps you could factor N = 3483199037737426090084842665153878458506048638439016353714695861794863252354872716815648422167549634981170589561810105410226481425840126372542074168393 as an example (151 digits) which is of the form above.


---

