factorization of "almost" prime numbers

2012-05-30, 06:27

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

Batalov · 2012-05-30, 06:41

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.

2012-05-30, 07:21

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

Dubslow · 2012-05-30, 07:27

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.

science_man_88 · 2012-05-30, 12:01

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.

LaurV · 2012-05-30, 12:09

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

science_man_88 · 2012-05-30, 12:15

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.

LaurV · 2012-05-30, 13:00

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

2012-05-30, 13:33

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.

akruppa · 2012-05-30, 14:09

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.

bsquared · 2012-05-30, 14:13

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.

2012-05-30, 06:27	#1
Ryan 2×23×31 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 3⁶×13 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, 12:09	#6
LaurV Romulan Interpreter Jun 2011 Thailand 7×1,373 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, 13:00	#8
LaurV Romulan Interpreter Jun 2011 Thailand 9611₁₀ 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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Aouessare-El Haddouchi-Essaaidi "test": "if Mp has no factor, it is prime!"	wildrabbitt	Miscellaneous Math	11	2015-03-06 08:17
"Quadratic time factorization" patent	mickfrancis	Factoring	5	2015-02-17 14:27
Looking for PrimeKit from "Prime Numbers A Computational Perspective"	gszpetkowski	Factoring	13	2014-08-05 11:57
"prime numbers formula" crankery	Mini-Geek	Miscellaneous Math	12	2009-03-04 16:51
Would Minimizing "iterations between results file" may reveal "is not prime" earlier?	nitai1999	Software	7	2004-08-26 18:12

2012-05-30, 07:21	#3
Ryan 9,109 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<A<43 -89<O<-88 16065₈ Posts	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.

2012-05-30, 13:33	#9
Ryan D07₁₆ 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.