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[/code]

Thanks a lot! :D

Ryan

If this is a homework assignment, then it would be inappropriate if someone just "solved it" for you.

You want to start for example [URL="http://gilchrist.ca/jeff/factoring/nfs_beginners_guide.html"]here[/URL], and then ask questions.

You can also check the [URL="http://factordb.com/index.php?query=142768380162790674658875061143813449127222076100248089061609390532042891100249724397498667660490250873113539420661"]FactorDB[/URL], 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. [URL="http://sourceforge.net/projects/yafu/"]yafu[/URL], that will definitely solve your problem and most likely in under one day.

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 :))

He'll either need to get ggnfs as well and/or GMP-ECM 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.

[QUOTE=Ryan;300679]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[/QUOTE]


are you sure this is an [URL="http://mathworld.wolfram.com/AlmostPrime.html"]almost prime[/URL] ?

all I'll add is it's 2^375+65811336810457707447392560948220453414175710337620263538272879976875465765294234922080178881418150012163094127093

there's been a talk about certain numbers put in this form.

Well, my comma (like a question mark, but much smaller) is about where the number is coming from, and especially [B]how do you know that the number is "almost" prime[/B]? (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

[QUOTE=LaurV;300695]Well, my comma (like a question mark, but much smaller) is about where the number is coming from, and especially [B]how do you know that the number is "almost" prime[/B]? (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...[/QUOTE]

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.

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

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.

[QUOTE=Ryan;300700]This is not homework[/QUOTE]

[QUOTE=Ryan;300700]We have these challenges and whoever gets the answer first gets points for it.[/QUOTE]

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.

[QUOTE=Ryan;300700]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.[/QUOTE]

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.