20120530, 06:27  #1 
2^{2}·3·5·163 Posts 
factorization of "almost" prime numbers
Hello everybody! I'm hoping somebody can help me. I have a really large number (> 100 digits) which I have to break down into prime factors. Searching the web I came upon this forum and I really hope somebody can solve this for me.
this is the number: Code:
142768380162790674658875061143813449127222076100248089061609390532042891100249724397498667660490250873113539420661 Ryan Last fiddled with by wblipp on 20120530 at 12:18 Reason: code tags 
20120530, 06:41  #2 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2^{2}·2,393 Posts 
If this is a homework assignment, then it would be inappropriate if someone just "solved it" for you.
You want to start for example here, and then ask questions. You can also check the FactorDB, which will tell you that indeed this is a valid miniproblem: this number is composite and is not yet factored. There are also some complete factorization packages, e.g. yafu, that will definitely solve your problem and most likely in under one day. Last fiddled with by Batalov on 20120530 at 06:49 Reason: yafu 
20120530, 07:21  #3 
6774_{10} Posts 
I was actually trying to use MSIEVE and GGNFS before but I couldn't find any guides on how to get it to work. that's why I just posted the question. But thanks for that, I'm giving it a try and hopefully will get it to work. If not I'll be back :))

20120530, 07:27  #4 
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
3·29·83 Posts 
He'll either need to get ggnfs as well and/or GMPECM if he wants to use multiple cores for ECM.
PS It would be a really crappy homework problem. PPS Ryan, you may want to reconsider your post's title. 
20120530, 12:01  #5  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
Quote:
are you sure this is an almost prime ? all I'll add is it's 2^375+65811336810457707447392560948220453414175710337620263538272879976875465765294234922080178881418150012163094127093 there's been a talk about certain numbers put in this form. Last fiddled with by science_man_88 on 20120530 at 12:21 

20120530, 12:09  #6 
Romulan Interpreter
"name field"
Jun 2011
Thailand
263B_{16} Posts 
Well, my comma (like a question mark, but much smaller) is about where the number is coming from, and especially how do you know that the number is "almost" prime? (whatever that means, kalmostprime? semiprime? brilliant?). Because if you know that, it means that the guy who gave you the problem knew the factors (!?) and it may be a real homework... otherwise you are up to some nogood things, like the guy who wanted to crack Battle.net few weeks ago...
I am running some nfs on it just for curiosity... edit: cross post with SM Last fiddled with by LaurV on 20120530 at 12:12 
20120530, 12:15  #7  
"Forget I exist"
Jul 2009
Dumbassville
20300_{8} Posts 
Quote:


20120530, 13:00  #8 
Romulan Interpreter
"name field"
Jun 2011
Thailand
9,787 Posts 
that's clear, but not all "almost primes" are difficult to factor. In fact, 99.9999...9999% of the numbers at this size are easy to (partially) factor, half of them are divisible by 2, a third of the remaining are divisible by 3, etc... For a big p, then 2p, 3p, 7p, etc are "almost" prime. But when you think about a number difficult to factor, generally you think about a semiprime with comparable size of factors, or better to a brilliant number. Saying you try to factor "almost primes" does not look interesting at all. They ALL contain small factors (the "density" of the set which do not contain small factors is zero)...
Last fiddled with by LaurV on 20120530 at 13:54 
20120530, 13:33  #9 
2×7×373 Posts 
This is not homework, it's for a course I'm doing in computer and network security at uni. We have these challenges and whoever gets the answer first gets points for it. One of the questions is to find the prime factors of the given number. I mean we're obviously meant to be using some program, so if somebody knows a way to get the answer quickly or can just give me the answer I would really appreciate it.

20120530, 14:09  #10  
"Nancy"
Aug 2002
Alexandria
2467_{10} Posts 
Quote:
YAFU, Msieve and GGNFS have already been mentioned, all of which will get you the answer quickly. I hope you don't expect someone to invest their CPU time to do your homework for you. 

20120530, 14:13  #11  
"Ben"
Feb 2007
6772_{8} Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
AouessareEl HaddouchiEssaaidi "test": "if Mp has no factor, it is prime!"  wildrabbitt  Miscellaneous Math  11  20150306 08:17 
"Quadratic time factorization" patent  mickfrancis  Factoring  5  20150217 14:27 
Looking for PrimeKit from "Prime Numbers A Computational Perspective"  gszpetkowski  Factoring  13  20140805 11:57 
"prime numbers formula" crankery  MiniGeek  Miscellaneous Math  12  20090304 16:51 
Would Minimizing "iterations between results file" may reveal "is not prime" earlier?  nitai1999  Software  7  20040826 18:12 