<p>Hart's <a href="http://wrap.warwick.ac.uk/54707/1/WRAP_Hart_S1446788712000146a.pdf" rel="nofollow noreferrer">one-line factorization algorithm</a> can do it in 150 microseconds with my unoptimized implementation (in <a href="https://pari.math.u-bordeaux.fr/" rel="nofollow noreferrer">PARI/GP</a>):</p>
<pre><code>olf(n,iter)=for(i=1,iter,my(s=sqrtint(n*i-1)+1,m=s^2%n,t);if(issquare(m,&amp;t),return(gcd(n,s-t))))
olf((2^1024+643)*(2^1028+187), 100)
</code></pre>

CC BY-SA 4.0
2023-04-13T15:02:06.657Z
You can cut the time in half by using the variant in section 3 of the paper.
Charles
CC BY-SA 4.0
2023-07-04T22:52:41.930Z
https://youtu.be/J-XxkA2WhXk
user68942
CC BY-SA 4.0
2023-04-13T14:35:25.753Z
2023-04-13T14:35:25.753Z
Charles
<p>yes, it can be done and in a very short time.</p>
<p>follow these steps and you will have the answer you are looking for</p>
<p>I show you how:</p>
<p>p=(2^1024-1)+644</p>
<p>q=(2^1028-1)+188</p>
<p>N=pq</p>
<p>X=998737</p>
<p>C=719077253944926363091722076315609893447190791576922629093720324630930703222003852530833909289630144084480455519485573430635159075257666489971389722557896497511071573699461941105208878404984376477812331808340023075352602729369851525895652442163308948653402042738345192959788983753918865219341425318496895550173</p>
<p>A=N Mod(C)</p>
<p>B=N-A</p>
<p>Mcd(A+CX,B-CX)=p</p>
<p>I await comments</p>

CC BY-SA 4.0
2023-04-13T18:25:31.467Z
C = 2^1026 - 998691 = 2^1026 - X + 46
Charles
CC BY-SA 4.0
2023-04-14T12:50:49.827Z
I can’t make any sense whatsoever of either the question or this answer. Are you claiming that this is a general semiprime factoring algorithm? If yes, where did the magic constants X and C come from? If not, then what’s the point? Surely if the goal is just to give a sequence of instructions that will compute factors of the specific number $((2^{1024}-1)+644)((2^{1028}-1)+188)$, the easiest way is `print 2^1024+643, 2^1028+187`?
Emil Jeřábek
CC BY-SA 4.0
2023-04-15T19:29:57.377Z
I can't answer you here because my answer is too long. So I added an answer to my question
user68942
CC BY-SA 4.0
2023-04-08T08:01:58.663Z
2023-04-08T08:04:22.043Z
2023-04-08T08:04:22.043Z
user68942
<p>If I tried to factor a semiprime as the product of the two prime factors given below in the form pq on a home computer would I be successful?</p>
<p>p=(2^1024-1)+644  prime factor
q=(2^1028-1)+188 prime factor</p>
<p>thanks for the replies</p>

CC BY-SA 4.0
2023-04-07T11:30:34.537Z
Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer.
Community
CC BY-SA 4.0
2023-04-07T16:19:54.533Z
Feed it with this semiprime: 253630045503841601190019425078101873844891259427547116272721 and let us know the result.
Marzio De Biasi
CC BY-SA 4.0
2023-04-07T20:50:56.057Z
I didn't understand the answer but ok.          366843387617597212562794266547, 691385081658413817748016689643                     can i have an answer now?
user68942
CC BY-SA 4.0
2023-04-14T11:04:59.183Z
@user68942: forget it, I thought you made a fast program for factoring so my intent was to give a hard to factor semiprime, but completely missed its size (it should be 1024 digits long)
Marzio De Biasi
CC BY-SA 4.0
2023-04-15T19:24:19.753Z
I was waiting for someone to answer to ask the right question about factoring.
the first question was a provocation to get an answer from a person capable of factoring large numbers. I ask now. Are you able to factor this semiprime in a short time?
102871258271817087746588121936639673713684691781048528382987839424506956640621905621689594929571101784228432009538937742027037369152353064318406162591788964666631606887709372155070888201286038306802082382484546985661473351057 I am able to factor it in a short time. If your answer is positive then you have answered my question. On the contrary, if it
user68942
CC BY-SA 4.0
2023-06-10T09:13:09.773Z
@MarzioDeBiasi Maybe you should see this and probably yes, it's a new factorization program that factorizes what other factorization programs don't factorize. https://youtu.be/gjED9D4gkfI
user68942
<ds.algorithms><nt.number-theory><factoring><primes>
pq factorization
user68942
# pq factorization

(Asked by: username_0 on 2023-04-06)

If I tried to factor a semiprime as the product of the two prime factors given below in the form pq on a home computer would I be successful?

p=(2^1024-1)+644 prime factor
q=(2^1028-1)+188 prime factor

thanks for the replies

**Tags:** ds.algorithms, nt.number-theory, factoring, primes

> **Comments:**
> **username_1**: Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer.  
> **username_2**: Feed it with this semiprime: 253630045503841601190019425078101873844891259427547116272721 and let us know the result.  
> **username_0**: I didn't understand the answer but ok.          366843387617597212562794266547, 691385081658413817748016689643                     can i have an answer now?  
> **username_2**: @username_0: forget it, I thought you made a fast program for factoring so my intent was to give a hard to factor semiprime, but completely missed its size (it should be 1024 digits long)  
> **username_0**: I was waiting for someone to answer to ask the right question about factoring. the first question was a provocation to get an answer from a person capable of factoring large numbers. I ask now. Are you able to factor this semiprime in a short time? 102871258271817087746588121936639673713684691781048528382987839424506956640621905621689594929571101784228432009538937742027037369152353064318406162591788964666631606887709372155070888201286038306802082382484546985661473351057 I am able to factor it in a short time. If your answer is positive then you have answered my question. On the contrary, if it  
> **username_0**: @MarzioDeBiasi Maybe you should see this and probably yes, it's a new factorization program that factorizes what other factorization programs don't factorize. https://youtu.be/gjED9D4gkfI  

---

## 2 answers

### Answer by username_3 on 2023-04-13. Score: 2

Hart's one-line factorization algorithm can do it in 150 microseconds with my unoptimized implementation (in PARI/GP):
olf(n,iter)=for(i=1,iter,my(s=sqrtint(n*i-1)+1,m=s^2%n,t);if(issquare(m,&t),return(gcd(n,s-t))))
olf((2^1024+643)*(2^1028+187), 100)

> **Comments:**
> **username_3**: You can cut the time in half by using the variant in section 3 of the paper.  
> **username_0**: https://youtu.be/J-XxkA2WhXk  

---

### Answer by username_0 on 2023-04-08. Score: -2

yes, it can be done and in a very short time.

follow these steps and you will have the answer you are looking for

I show you how:

p=(2^1024-1)+644

q=(2^1028-1)+188

N=pq

X=998737

C=719077253944926363091722076315609893447190791576922629093720324630930703222003852530833909289630144084480455519485573430635159075257666489971389722557896497511071573699461941105208878404984376477812331808340023075352602729369851525895652442163308948653402042738345192959788983753918865219341425318496895550173

A=N Mod(C)

B=N-A

Mcd(A+CX,B-CX)=p

I await comments

> **Comments:**
> **username_3**: C = 2^1026 - 998691 = 2^1026 - X + 46  
> **username_4**: I can’t make any sense whatsoever of either the question or this answer. Are you claiming that this is a general semiprime factoring algorithm? If yes, where did the magic constants X and C come from? If not, then what’s the point? Surely if the goal is just to give a sequence of instructions that will compute factors of the specific number $((2^{1024}-1)+644)((2^{1028}-1)+188)$, the easiest way is `print 2^1024+643, 2^1028+187`?  
> **username_0**: I can't answer you here because my answer is too long. So I added an answer to my question  

---

