mersenneforum.org factorization of "almost" prime numbers
 Register FAQ Search Today's Posts Mark Forums Read

 2012-05-30, 06:27 #1 Ryan   22·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 Thanks a lot! :D Ryan Last fiddled with by wblipp on 2012-05-30 at 12:18 Reason: code tags
 2012-05-30, 06:41 #2 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 22·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 mini-problem: 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 2012-05-30 at 06:49 Reason: yafu
 2012-05-30, 07:21 #3 Ryan   677410 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 :))
 2012-05-30, 07:27 #4 Dubslow Basketry That Evening!     "Bunslow the Bold" Jun 2011 40
2012-05-30, 12:01   #5
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by Ryan 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: 142768380162790674658875061143813449127222076100248089061609390532042891100249724397498667660490250873113539420661 Thanks a lot! :D Ryan

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 2012-05-30 at 12:21

 2012-05-30, 12:09 #6 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 263B16 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, k-almost-prime? semi-prime? 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 no-good 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 2012-05-30 at 12:12
2012-05-30, 12:15   #7
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

203008 Posts

Quote:
 Originally Posted by LaurV 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, k-almost-prime? semi-prime? 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 no-good things, like the guy who wanted to crack Battle.net few weeks ago... I am running some nfs on it just for curiosity...
well every composite to my knowledge fits into the first group the second group seems a subset of the first the third is a special subset of the second.

 2012-05-30, 13:00 #8 LaurV 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 2012-05-30 at 13:54
 2012-05-30, 13:33 #9 Ryan   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.
2012-05-30, 14:09   #10
akruppa

"Nancy"
Aug 2002
Alexandria

246710 Posts

Quote:
 Originally Posted by Ryan This is not homework
Quote:
 Originally Posted by Ryan We have these challenges and whoever gets the answer first gets points for it.
It's not homework, but it's an assignment to solve at home that earns you credit?

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.

2012-05-30, 14:13   #11
bsquared

"Ben"
Feb 2007

67728 Posts

Quote:
 Originally Posted by Ryan 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.
Solving a problem that will benefit you in a classroom setting sounds like homework to me. The hints given so far will will allow you to solve it in a day or less with access to any average computer.

 Similar Threads Thread Thread Starter Forum Replies Last Post wildrabbitt Miscellaneous Math 11 2015-03-06 08:17 mickfrancis Factoring 5 2015-02-17 14:27 gszpetkowski Factoring 13 2014-08-05 11:57 Mini-Geek Miscellaneous Math 12 2009-03-04 16:51 nitai1999 Software 7 2004-08-26 18:12

All times are UTC. The time now is 11:28.

Mon Oct 25 11:28:47 UTC 2021 up 94 days, 5:57, 0 users, load averages: 0.73, 0.84, 0.93