<p>(This would be more suited as a comment, but I don't have enough reputation to post one)</p>
<p>As someone already posted in the comments:
303960069878176128824759747828233142542271721553435748471796998430775237581596664345307168958756178750378400951704796839644199408595192763805668220031073147599703672819906623774589708408280533055310101005133640327782674190629191232920645549281694972445510003833 = 52303351985351619139135314583749349952533094847115157805364693325945342735900478773908720210328648815667828249346672146758202758849 x 5811483553927957682126146064861038883614788316346128645040521480660593637322275419323191134480960979518647583260741349639800306617</p>
<p>Another number you posted in comments:
1737308314051321188153737760718651536153003874190659056877100871667078366232891487026153897841099765525840472053348405269454221681971374832586973594416556129745846754663897982461531815950851453761625191777603012444690161655312710151772391456005953869233300346722988483149878875164794354652479777495939429032770945148823 = 61640029873696844587354495248467655238959604866138307074477812999899122146583802168656575797599660327192763477246946112810148535313507889074737242512454360455707 * 28184741597483696656312069157964177063996161347113995004333705075399690053307637022705338727754760094738346354479627852222290139603798760436551093970029428789</p>
<p>The special property of both of these numbers is that, denoting <span class="math-container">$p$</span> and <span class="math-container">$q$</span> as prime factors, <span class="math-container">$p &lt; q$</span>: <span class="math-container">$q \equiv a \mod p$</span>, and <span class="math-container">$\mid a \mid$</span> is a small value.</p>
<p>We can verify that this holds for above integers:
52303351985351619139135314583749349952533094847115157805364693325945342735900478773908720210328648815667828249346672146758202758849 <span class="math-container">$\equiv$</span> -704 (mod 52303351985351619139135314583749349952533094847115157805364693325945342735900478773908720210328648815667828249346672146758202758849)</p>
<p>61640029873696844587354495248467655238959604866138307074477812999899122146583802168656575797599660327192763477246946112810148535313507889074737242512454360455707 <span class="math-container">$\equiv$</span> -305836 (mod 28184741597483696656312069157964177063996161347113995004333705075399690053307637022705338727754760094738346354479627852222290139603798760436551093970029428789)</p>
<p>Composite numbers (not necessarily semiprimes) of this form can be factored via <a href="https://programmingpraxis.com/2017/08/22/lehmans-factoring-algorithm/" rel="nofollow noreferrer">Lehmann's factorization algorithm</a> quite efficiently, as long as <span class="math-container">$\frac{q}{p}$</span> is not too large. Some adjustments need to be made in case of large integers such as yours, i.e. the iteration range of the <code>a</code> variable should be much shorter, but in principle the factors can be found very quickly. The reason why standard algorithms don't perform well on such integers is that they're meant for general-purpose factorization, while integers that have the special property mentioned above are a very small fraction of all integers and don't warrant any special handling in general-purpose methods.</p>

CC BY-SA 4.0
2023-05-25T23:17:35.293Z
Thanks for the reply, very interesting. Non posso darti il semiprimo perchè non c'è spazio ma ti darò i fattori con cui è stato creato (3^501+37967446) * (2^801+36181439). Cosa mi dici di questo e del perchè nessun algoritmo conosciuto riesce a fattorizzarlo?
user68942
CC BY-SA 4.0
2023-06-10T08:49:44.737Z
@inwarx Thanks for the reply. Do you think you can factor numbers like those presented in this video by modifying the Lehmann factorization algorithm?  https://youtu.be/gjED9D4gkfI
user68942
CC BY-SA 4.0
2023-05-21T17:21:12.797Z
2023-05-21T17:21:12.797Z
ynwarcs
<p>I didn't get a reply to my previous post maybe because my question was too stupid?</p>
<p>I'm asking this forum for help in understanding how far we are from factoring very large semiprimes</p>
<p>I'll try to repeat the question more intelligently:
Can anyone factor this number using any calculation program such as Pari/GP, Sympy, Yafo, or any other program?</p>
<p>If yes, please tell me what it was factored with, if not, tell me why it can't be factored.</p>
<p>thank you very much to anyone who will answer seriously.</p>
<p>303960069878176128824759747828233142542271721553435748471796998430775237581596664345307168958756178750378400951704796839644199408595192763805668220031073147599703672819906623774589708408280533055310101005133640327782674190629191232920645549281694972445510003833</p>

CC BY-SA 4.0
2023-05-06T10:54:01.453Z
Are you aware of the RSA crypto-system, and how it relates to semi-prime factorisation?
Martin Berger
CC BY-SA 4.0
2023-05-06T10:57:50.063Z
Not sure why, but ECM can factor this number very quickly (I used [this](https://www.alpertron.com.ar/ECM.HTM) website) — 5811 483553 927957 682126 146064 861038 883614 788316 346128 645040 521480 660593 637322 275419 323191 134480 960979 518647 583260 741349 639800 306617 × 52303 351985 351619 139135 314583 749349 952533 094847 115157 805364 693325 945342 735900 478773 908720 210328 648815 667828 249346 672146 758202 758849
Command Master
CC BY-SA 4.0
2023-05-06T17:32:43.287Z
Thank you very much. The link you gave me is really good. Yes, exactly, these are the factors. The reason is that I need to test an algorithm created by me that allows me to factor large numbers. What I posted was a small semiprime compared to what I can factor with my algorithm.I tried to test one of my biggest semi-primes and after 11 minutes I stopped it because I factor it in less than a second. It will still be a great comparison test. If you want to see the semiprime that I factored, I'll post it in the main post
user68942
CC BY-SA 4.0
2023-05-06T17:41:49.330Z
The answer was very useful and unfortunately I have to post here the second semi-first that I would like to be tested because it is really great. 1283268508691738412749092478651116158445295667058801504229212422570308422835899086073086423288542071666186967047132272091068352369086434620824367793167803449347622545333810259970429173424487887444853291081769657239932326073036616470273433412342144710412390541266462627229134766949777211815907189209754968256089463520662870164288156112072534651149434848578490527310083423555578798294533472212505297087660624255332533001416037832168080131586023260919817581
user68942
CC BY-SA 4.0
2023-05-07T03:31:34.997Z
The [RSA numbers](https://en.wikipedia.org/wiki/RSA_numbers) are a set of randomly generated semiprimes which are used to benchmark factoring. The largest one factored to date is RSA-250, which has 250 decimal digits. Your number is about 7 times longer, and completely impractical to factor with known algorithms assuming it was generated randomly.
Command Master
CC BY-SA 4.0
2023-05-07T08:51:46.770Z
My number isn't random, it's just a big number that algorithms currently out there can't factor into. What I wanted to understand was what scientific interest is behind these factorizations. The only interest I've seen behind this research is in solving RSA semiprimes. A new algorithm that solves numbers like these but doesn't solve RSA numbers attracts no interest. Thanks for everything
user68942
CC BY-SA 4.0
2023-05-07T16:24:09.587Z
Wdym by not random? What special properties does it have? There is research to special-purpose factoring algorithms.
Command Master
CC BY-SA 4.0
2023-05-07T17:33:30.663Z
I'm Italian and you've probably noticed that what I write I translate with a translator. if I can write in Italian it would be easier for me to write. La ricerca che sto facendo è veramente molto interessante. Per adesso non posso dirti molto ma mi piacerebbe continuare a parlarne. Quello che ti posso dire è che ogni giorno scopro qualcosa di nuovo e la proprietà che ho trovato si sta rivelando incredibilmente potente. Solo fino a ieri non potevo a fattorizzare questo numero che posterò nelle mie risposte.
user68942
CC BY-SA 4.0
2023-05-07T17:38:07.270Z
Il numero che adesso riesco a fattorizzare e che solo ieri non riuscivo è questo
1737308314051321188153737760718651536153003874190659056877100871667078366232891487026153897841099765525840472053348405269454221681971374832586973594416556129745846754663897982461531815950851453761625191777603012444690161655312710151772391456005953869233300346722988483149878875164794354652479777495939429032770945148823 Ho provato con il link che mi è stato dato e non riesce a fattorizzarlo, così anche pari/gp e sympy,, almeno non ci riescono in breve tempo. Io fattorizzo questo in qualche secondo
user68942
CC BY-SA 4.0
2023-05-18T15:09:48.653Z
@CommandMaster That is extremely interesting; normally ECM could never find such large factors. This clearly speaks to how unusual the number is. Can anyone characterize what about this number allows this to happen?
Charles
CC BY-SA 4.0
2023-05-18T15:12:43.203Z
@user68942 Can your method factor arbitrary numbers like, say, 6528406589185691801016441717439226347148297379827134742115115845247538852245816250852355397731250024911786019? This is pretty small (110 digits) but lacks the special characteristics of the number your asked about.
Charles
CC BY-SA 4.0
2023-05-25T22:55:16.627Z
Purtroppo non riesco a risponderti perchè ho bisogno di spazio per le risposte e qui non me lo permettono. Questo numero non riesco a fattorizzarlo ma se vuoi una risposta più precisa del perchè posta i suoi due fattori. se questi sono vicini alle specifiche RSA in questo caso non riesco. I numeri che io fattorizzo nessun algoritmo conosciuto riesce a fattorizzarli ma allo stesso stempo anche io non riesco a fattorizzare molti che invece loro fattorizzano.
user68942
<reference-request><factoring>
factoring large numbers
user68942
# factoring large numbers

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

I didn't get a reply to my previous post maybe because my question was too stupid?

I'm asking this forum for help in understanding how far we are from factoring very large semiprimes

I'll try to repeat the question more intelligently:
Can anyone factor this number using any calculation program such as Pari/GP, Sympy, Yafo, or any other program?

If yes, please tell me what it was factored with, if not, tell me why it can't be factored.

thank you very much to anyone who will answer seriously.

303960069878176128824759747828233142542271721553435748471796998430775237581596664345307168958756178750378400951704796839644199408595192763805668220031073147599703672819906623774589708408280533055310101005133640327782674190629191232920645549281694972445510003833

**Tags:** reference-request, factoring
> **Comments:**
> **username_1**: Are you aware of the RSA crypto-system, and how it relates to semi-prime factorisation?  
> **username_2**: Not sure why, but ECM can factor this number very quickly (I used [this](https://www.alpertron.com.ar/ECM.HTM) website) — 5811 483553 927957 682126 146064 861038 883614 788316 346128 645040 521480 660593 637322 275419 323191 134480 960979 518647 583260 741349 639800 306617 × 52303 351985 351619 139135 314583 749349 952533 094847 115157 805364 693325 945342 735900 478773 908720 210328 648815 667828 249346 672146 758202 758849  
> **username_0**: Thank you very much. The link you gave me is really good. Yes, exactly, these are the factors. The reason is that I need to test an algorithm created by me that allows me to factor large numbers. What I posted was a small semiprime compared to what I can factor with my algorithm.I tried to test one of my biggest semi-primes and after 11 minutes I stopped it because I factor it in less than a second. It will still be a great comparison test. If you want to see the semiprime that I factored, I'll post it in the main post  
> **username_0**: The answer was very useful and unfortunately I have to post here the second semi-first that I would like to be tested because it is really great. 1283268508691738412749092478651116158445295667058801504229212422570308422835899086073086423288542071666186967047132272091068352369086434620824367793167803449347622545333810259970429173424487887444853291081769657239932326073036616470273433412342144710412390541266462627229134766949777211815907189209754968256089463520662870164288156112072534651149434848578490527310083423555578798294533472212505297087660624255332533001416037832168080131586023260919817581  
> **username_2**: The [RSA numbers](https://en.wikipedia.org/wiki/RSA_numbers) are a set of randomly generated semiprimes which are used to benchmark factoring. The largest one factored to date is RSA-250, which has 250 decimal digits. Your number is about 7 times longer, and completely impractical to factor with known algorithms assuming it was generated randomly.  
> **username_0**: My number isn't random, it's just a big number that algorithms currently out there can't factor into. What I wanted to understand was what scientific interest is behind these factorizations. The only interest I've seen behind this research is in solving RSA semiprimes. A new algorithm that solves numbers like these but doesn't solve RSA numbers attracts no interest. Thanks for everything  
> **username_2**: Wdym by not random? What special properties does it have? There is research to special-purpose factoring algorithms.  
> **username_0**: I'm Italian and you've probably noticed that what I write I translate with a translator. if I can write in Italian it would be easier for me to write. La ricerca che sto facendo è veramente molto interessante. Per adesso non posso dirti molto ma mi piacerebbe continuare a parlarne. Quello che ti posso dire è che ogni giorno scopro qualcosa di nuovo e la proprietà che ho trovato si sta rivelando incredibilmente potente. Solo fino a ieri non potevo a fattorizzare questo numero che posterò nelle mie risposte.  
> **username_0**: Il numero che adesso riesco a fattorizzare e che solo ieri non riuscivo è questo 1737308314051321188153737760718651536153003874190659056877100871667078366232891487026153897841099765525840472053348405269454221681971374832586973594416556129745846754663897982461531815950851453761625191777603012444690161655312710151772391456005953869233300346722988483149878875164794354652479777495939429032770945148823 Ho provato con il link che mi è stato dato e non riesce a fattorizzarlo, così anche pari/gp e sympy,, almeno non ci riescono in breve tempo. Io fattorizzo questo in qualche secondo  
> **username_3**: @CommandMaster That is extremely interesting; normally ECM could never find such large factors. This clearly speaks to how unusual the number is. Can anyone characterize what about this number allows this to happen?  
> **username_3**: @user68942 Can your method factor arbitrary numbers like, say, 6528406589185691801016441717439226347148297379827134742115115845247538852245816250852355397731250024911786019? This is pretty small (110 digits) but lacks the special characteristics of the number your asked about.  
> **username_0**: Purtroppo non riesco a risponderti perchè ho bisogno di spazio per le risposte e qui non me lo permettono. Questo numero non riesco a fattorizzarlo ma se vuoi una risposta più precisa del perchè posta i suoi due fattori. se questi sono vicini alle specifiche RSA in questo caso non riesco. I numeri che io fattorizzo nessun algoritmo conosciuto riesce a fattorizzarli ma allo stesso stempo anche io non riesco a fattorizzare molti che invece loro fattorizzano.  

---

## 1 answers

### Answer by username_4 on 2023-05-21. Score: 1

(This would be more suited as a comment, but I don't have enough reputation to post one)

As someone already posted in the comments:
303960069878176128824759747828233142542271721553435748471796998430775237581596664345307168958756178750378400951704796839644199408595192763805668220031073147599703672819906623774589708408280533055310101005133640327782674190629191232920645549281694972445510003833 = 52303351985351619139135314583749349952533094847115157805364693325945342735900478773908720210328648815667828249346672146758202758849 x 5811483553927957682126146064861038883614788316346128645040521480660593637322275419323191134480960979518647583260741349639800306617

Another number you posted in comments:
1737308314051321188153737760718651536153003874190659056877100871667078366232891487026153897841099765525840472053348405269454221681971374832586973594416556129745846754663897982461531815950851453761625191777603012444690161655312710151772391456005953869233300346722988483149878875164794354652479777495939429032770945148823 = 61640029873696844587354495248467655238959604866138307074477812999899122146583802168656575797599660327192763477246946112810148535313507889074737242512454360455707 \* 28184741597483696656312069157964177063996161347113995004333705075399690053307637022705338727754760094738346354479627852222290139603798760436551093970029428789

The special property of both of these numbers is that, denoting $p$ and $q$ as prime factors, $p < q$: $q \equiv a \mod p$, and $\mid a \mid$ is a small value.

We can verify that this holds for above integers:
52303351985351619139135314583749349952533094847115157805364693325945342735900478773908720210328648815667828249346672146758202758849 $\equiv$ -704 (mod 52303351985351619139135314583749349952533094847115157805364693325945342735900478773908720210328648815667828249346672146758202758849)

61640029873696844587354495248467655238959604866138307074477812999899122146583802168656575797599660327192763477246946112810148535313507889074737242512454360455707 $\equiv$ -305836 (mod 28184741597483696656312069157964177063996161347113995004333705075399690053307637022705338727754760094738346354479627852222290139603798760436551093970029428789)

Composite numbers (not necessarily semiprimes) of this form can be factored via [Lehmann's factorization algorithm](https://programmingpraxis.com/2017/08/22/lehmans-factoring-algorithm/) quite efficiently, as long as $\frac{q}{p}$ is not too large. Some adjustments need to be made in case of large integers such as yours, i.e. the iteration range of the `a` variable should be much shorter, but in principle the factors can be found very quickly. The reason why standard algorithms don't perform well on such integers is that they're meant for general-purpose factorization, while integers that have the special property mentioned above are a very small fraction of all integers and don't warrant any special handling in general-purpose methods.

> **Comments:**
> **username_0**: Thanks for the reply, very interesting. Non posso darti il semiprimo perchè non c'è spazio ma ti darò i fattori con cui è stato creato (3^501+37967446) * (2^801+36181439). Cosa mi dici di questo e del perchè nessun algoritmo conosciuto riesce a fattorizzarlo?  
> **username_0**: @inwarx Thanks for the reply. Do you think you can factor numbers like those presented in this video by modifying the Lehmann factorization algorithm?  https://youtu.be/gjED9D4gkfI  

---

