Factoring Integers Question
 

Hello everybody,

I'm a young researcher and I found your site and it was very intresting for me. For now I don't anything about how to factor integers using the computer and I'm glad for your help :smile:

I will state here my personal laptop abilities even though I don't know which is important in factoring:
Windows Vista Home Premium, 32bit, Core 2 Duo CPU 1.80 GHz, 1GB RAM.
If there something you need to know please tell me :smile:

I have few questions:
1) Please can I know which factoring program is suitable for me? And what are the differences between factoring programs I mean like why this program is faster than that for example.

2) What affect the factoring speed.

3) Can I do all my factoring tests under the same conditions I mean does my open programs and my work will affect the process and if yes can I prepare the program to work in some conditions so I can do all my tests under the same conditions and abilities.

Thanks a lot for your helping :help: :smile:

The easiest way to get started is to join existing projects. There are two BOINC projects focused on factoring large integers. [URL="http://www.rechenkraft.net/yoyo/"]yoyo@home[/URL] hosts a number of projects, one of which is ECM factoring of numbers from the [URL="http://xyyxf.at.tut.by/"]XYYXF project[/URL]. ECM allows you to find relatively small factors of numbers. The speed of ECM depends mainly on the size of the factor and much less on the size of the original number. The other is [URL="http://escatter11.fullerton.edu/nfs/"]NFS@Home[/URL] [SIZE="1"](full disclosure: I am the admin of NFS@Home)[/SIZE] which distributes the sieving stage of the Number Field Sieve factoring algorithm. Unlike ECM, NFS can find much larger factors of numbers, but has a [I]much[/I] lower limit on the size of numbers that can be factored. The speed depends on the size of the number, not on the size of the factors.

What type of numbers are you interested in factoring? That will make a difference in the program that you will want to use.

Thanks a lot for your information.
I will write some details here:
I'm doing a small research on computers capabilities on integer factorization so I'm not interested in very big number that take a lot of time like a month or something or even a week. Like small number that take maximum a day and arrange them by their size and do the same on different computers but for now in my personal laptop. I hope I detailed enough if any detail is needed please ask me.

By the way how the number size get measured like xx bit. Is it how it is difficult or how is it long?

Thanks in advance

Note: I'm not interested in mersenne primes now but I want to factor like RSA numbers.

[quote=hasan4444;192998] By the way how the number size get measured like xx bit. Is it how it is difficult or how is it long?[/quote]
It's how long. More specifically, it's the number of [B]b[/B]inary dig[B]its[/B] (hence bits) the number has. (its length in base 2)
[quote=hasan4444;192998] Note: I'm not interested in mersenne primes now but I want to factor like RSA numbers.[/quote]
GNFS is the only practical way to factor RSA numbers, and to do it in a day on your laptop, you can't go above about 115 digits (around 380 bits).
Here's a beginner's guide to GNFS: [url]http://gilchrist.ca/jeff/factoring/nfs_beginners_guide.html[/url]
Here are some Windows binaries (.exe's) for various factoring apps: [url]http://gilchrist.ca/jeff/factoring/index.html[/url]

[quote=Mini-Geek;193005]
GNFS is the only practical way to factor RSA numbers, [/quote]

Well, now, he didn't say he wanted to factor particularly big RSA numbers, so this is QS territory as well.

You can factor an RSA number probably up to about 100 digits using QS in a day with your machine. 90 digits would take a few hours.

[url=http://bbuhrow.googlepages.com/home]yafu[/url] is probably the fastest tool for QS for your machine, and you can also use it to generate test RSA-like numbers. Anything bigger than 90 digits or so can probably be done faster with GNFS (with the right tools and the right configuration).

Thanks a lot guys
I have to take some of your time if you could
I downloaded yafu it works nice when I enter some commands like: siqs(xxxxxxxx...xxxx) and then he give me the factors but I have a question what this command means "siqs(rsa(200))" or any number it's not 200 digit RSA number for sure because it get computed so fast in less than half a minute and the digits are about 70???
I've seen wikipedia "http://en.wikipedia.org/wiki/RSA_numbers#RSA-100" I think this article has a typo or something because sometimes it indicate that RSA-(number) that this number indicates its bits and sometimes say that it's indicate its decimal digits.

Also I downloaded GNFS for P4 and 32bit and I have Core2 but in the site it says Core2 and 64bit so I decided to download P4 version. It's setup is so complicated I think I did what the site said but I'm not sure about running it what I did was:
Copying the extracted files in "C:\home\jeff\ggnfs" then I created "C:\home\jeff\ggnfs\example" and did as the site says for "example.n" inside this folder and I edited "factMsieve.pl" as well. I downloaded Cygwin but I don't know how to use it to run GNFS. Please tell me my mistake if you can or what should I do for this.

Thanks a lot for your time and your effort. Thanks a lot

[quote=hasan4444;193052]I have a question what this command means "siqs(rsa(200))" or any number it's not 200 digit RSA number for sure because it get computed so fast in less than half a minute and the digits are about 70???
[/quote]

rsa(xxx) gives back a number with xxx bits. 200 bits is about 60 decimal digits.

Thanks a lot but do you know what is meant when they write
RSA-100 or RSA-130
Is it the number of digits or the bits?
And is there a way to know how many bits in a particular number?
Thanks in advance

[QUOTE=hasan4444;193055]Thanks a lot but do you know what is meant when they write
RSA-100 or RSA-130
Is it the number of digits or the bits?
And is there a way to know how many bits in a particular number?
Thanks in advance[/QUOTE]
Could be either, it kinda depends on the context. You can probably dis-ambiguate them with the following rule of thumb (referring to the XXX in RSA-XXX). Less than 512 refers to decimal digits. Greater than 512 refers to bits. This is because typically no one is interested in factoring an RSA number less than 512 bits: it is too easy. Also no one is interested in factoring a number greater than 512 digits: it is too hard.
The convention (I believe) now is to always specify the number of bits... but several famous RSA numbers were defined with number of digits and so there is confusion.

Another rule of thumb is that if it ends in 0 it's probably referring to decimal digits, if it's ending in something else, and factors into many multiples of 2 like 512=2^9 or 768=2^8*3, then it's probably referring to bits.