mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2012-05-30, 06:27   #1
Ryan
 

22·3·5·163 Posts
Default 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
  Reply With Quote
Old 2012-05-30, 06:41   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22·2,393 Posts
Default

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
Batalov is offline   Reply With Quote
Old 2012-05-30, 07:21   #3
Ryan
 

677410 Posts
Default

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 :))
  Reply With Quote
Old 2012-05-30, 07:27   #4
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3·29·83 Posts
Default

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.
Dubslow is offline   Reply With Quote
Old 2012-05-30, 12:01   #5
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by Ryan View Post
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
science_man_88 is offline   Reply With Quote
Old 2012-05-30, 12:09   #6
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

263B16 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2012-05-30, 12:15   #7
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

203008 Posts
Default

Quote:
Originally Posted by LaurV View Post
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.
science_man_88 is offline   Reply With Quote
Old 2012-05-30, 13:00   #8
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

9,787 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2012-05-30, 13:33   #9
Ryan
 

2×7×373 Posts
Default

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.
  Reply With Quote
Old 2012-05-30, 14:09   #10
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

246710 Posts
Default

Quote:
Originally Posted by Ryan View Post
This is not homework
Quote:
Originally Posted by Ryan View Post
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.
akruppa is offline   Reply With Quote
Old 2012-05-30, 14:13   #11
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

67728 Posts
Default

Quote:
Originally Posted by Ryan View Post
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.
bsquared is offline   Reply With Quote
Reply

Thread Tools


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

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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.