-4
$\begingroup$

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

$\endgroup$
12
  • $\begingroup$ Are you aware of the RSA crypto-system, and how it relates to semi-prime factorisation? $\endgroup$ May 6, 2023 at 10:54
  • $\begingroup$ Not sure why, but ECM can factor this number very quickly (I used this 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 $\endgroup$ May 6, 2023 at 10:57
  • $\begingroup$ 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 $\endgroup$
    – user68942
    May 6, 2023 at 17:32
  • $\begingroup$ 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 $\endgroup$
    – user68942
    May 6, 2023 at 17:41
  • 1
    $\begingroup$ @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? $\endgroup$
    – Charles
    May 18, 2023 at 15:09

1 Answer 1

1
$\begingroup$

(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 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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – user68942
    May 25, 2023 at 23:17
  • $\begingroup$ @inwarx Thanks for the reply. Do you think you can factor numbers like those presented in this video by modifying the Lehmann factorization algorithm? youtu.be/gjED9D4gkfI $\endgroup$
    – user68942
    Jun 10, 2023 at 8:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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