mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2003-08-07, 00:09   #1
dsouza123
 
dsouza123's Avatar
 
Sep 2002

2·331 Posts
Default Different types of factoring, implementation

Types of factoring, aware of/interested in.

Prime95 style trial factoring to find a small prime factor to save the time of a more extensive prime test.

RSA style factoring find 2 large roughly equal size prime factors of a large number.

Complete factorization finding all the prime factors of a given number, trial factoring could be a starting point because it can give one of the factors.

NSFNET factoring using the NFS to find factors of large numbers usually of a n^p +/- d

The code/algorithms behind the factoring efforts is of great interest, for improvement, alternative theories, challenge of re-implementing it to understand the subtle issues of the algorithm.
dsouza123 is offline   Reply With Quote
Old 2003-08-07, 01:11   #2
TTn
 

100100011000102 Posts
Default Factors of remainders.

Mp is prime if it divides S(p-2) with S(0)=4. true

Mp is prime if it divides S(p-2) with S(0)=3, and p=3(mod4). true
Although it works with p=1(mod 4) up to 4500, but is not nessesarily true.


So, is Mp is probably prime if it divides the remainder R of :
[S(p-2) with S(0)=4] = R (mod [S(p-2) with S(0)=3] )

This has got to be faster than the current procedure at least when p=3(mod 4). Right? It could make for lone p=3(mod4) hunters.

:D



Edit, I posted this as a new topic, and it came out as a reply... hmmm
  Reply With Quote
Old 2003-08-07, 04:34   #3
NickGlover
 
NickGlover's Avatar
 
Aug 2002
Richland, WA

22×3×11 Posts
Default Re: Factors of remainders.

Quote:
Originally Posted by TTn
So, is Mp is probably prime if it divides the remainder R of :
[S(p-2) with S(0)=4] = R (mod [S(p-2) with S(0)=3] )

This has got to be faster than the current procedure at least when p=3(mod 4). Right? It could make for lone p=3(mod4) hunters.
Isn't [S(p-2) with S(0)=3] REALLY big? That would make very large and slow multiplies necessary.
NickGlover is offline   Reply With Quote
Old 2003-08-07, 08:10   #4
TTn
 

3×11×132 Posts
Default

Quote:
Isn't [S(p-2) with S(0)=3] REALLY big? That would make very large and slow multiplies necessary.
Not really, it is smaller than S(0)=4
The remainder between S(0)=3 & S(0)=4 is way smaller.
Besides I dont believe that these large numbers are actually divided.
The only catch I can think of is that the power algorithm may be different than that of S(0)=4. I'll check that out and repost later. (indeed)

BTW S(0)=3 are Lucas(Golden ratio) numbers possesing an index of a power of two.
3 7 47 2207 4870847... *2-2 *2-2 *2-2...
  Reply With Quote
Old 2003-08-07, 09:02   #5
Axel Fox
 
Axel Fox's Avatar
 
May 2003

25·3 Posts
Default

Actually, all the S(x) computations are done MOD 2^p - 1 . That means that wether you start with 3 or 4, as soon as the square is higher than Mp, you take the MOD, and there's not telling which one will be greater at that point (it will probably alternate), so the multiplication times would not make any difference appart from the first few iterations.

In my opinion, you will get a gain of a few milliseconds on the whole LL-Test.
Axel Fox is offline   Reply With Quote
Old 2003-08-07, 10:03   #6
NickGlover
 
NickGlover's Avatar
 
Aug 2002
Richland, WA

22·3·11 Posts
Default Re: Factors of remainders.

Quote:
Originally Posted by TTn
So, is Mp is probably prime if it divides the remainder R of :
[S(p-2) with S(0)=4] = R (mod [S(p-2) with S(0)=3] )
I guess I just don't understand the algorithm you're proposing. I understand how S(p-2) | S(0)=3 works by itself, but I don't think its clear what [ S(p-2) | S(0)=4 ] = R ( mod [ S(p-2) | S(0)=3 ] ) actually implies for the algorithm.

Are you proposing that you we caculate S(p-2) | S(0)=3 first and then do S(p-2) | S(0)=4 mod that?

Or are you suggesting that we calculate [ S(1) | S(0)=4 ] ( mod [ S(1) | S(0)=3 ] ), then [ S(2) | S(0)=4 ] ( mod [ S(2) | S(0)=3 ] ), etc.?
NickGlover is offline   Reply With Quote
Old 2003-08-07, 16:53   #7
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

32·112 Posts
Default Re: Different types of factoring, implementation

Quote:
Originally Posted by dsouza123
Types of factoring, aware of/interested in.

Prime95 ...
...
NSFNET factoring ...
You left out a major one.
There is money in this one.









"Raising Cash from Accounts Receivable"
Wacky is offline   Reply With Quote
Old 2003-08-07, 19:33   #8
dsouza123
 
dsouza123's Avatar
 
Sep 2002

2·331 Posts
Default

Yes,

Factoring in the AR sense, I had never heard of factoring in that sense until a few months ago when searching for factoring algorithms and the AR factoring was filling the search results.

I don't think it has much, if any, relation to factoring integers into their prime factors.

I prefer prime factorization. :)
dsouza123 is offline   Reply With Quote
Old 2003-08-07, 19:44   #9
Axel Fox
 
Axel Fox's Avatar
 
May 2003

25·3 Posts
Default

I'm not 100% sure, but I think Wackerbarth is referring to Factoring Fermat Numbers.

If you ever find a new one of a Fermat number with n between 12 and 22, don't forget to notify Perfectly Scientific Inc. and they will give you money for it.
Axel Fox is offline   Reply With Quote
Old 2003-08-07, 20:04   #10
dsouza123
 
dsouza123's Avatar
 
Sep 2002

2×331 Posts
Default

Factoring algorithms:

Brute force divide by odds ( or primes) <= square root (coded)

Trial factoring if bit[i] of p = 1 then *2 algorithm. (coded)

P-1 factoring.

ECM

Difference of two squares. (coded)

NFS (Number Field Seive) and it's predecessors.

Does anybody know of any other factoring algorithms ?

Ones that can be coded without needing an advanced understanding of number theory.

Any theories that could possibly be made into algorithms/heuristics/rules of thumb ?
dsouza123 is offline   Reply With Quote
Old 2003-08-07, 20:12   #11
ColdFury
 
ColdFury's Avatar
 
Aug 2002

26×5 Posts
Default

Quote:
Ones that can be coded without needing an advanced understanding of number theory.
You can code the Quadratic Sieve without much understanding of "why" it works.
ColdFury is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
SQUFOF implementation alpertron Factoring 15 2010-04-12 19:16
ECM/FPGA Implementation rdotson Hardware 12 2006-03-26 22:58
need C implementation of divb(r,k) Leith Miscellaneous Math 4 2005-01-18 23:14
RSA implementation flava Programming 12 2004-10-26 03:51
Types of work to request from server : Add P-1 Factoring MoZ Software 2 2004-02-06 20:24

All times are UTC. The time now is 23:39.

Sun Apr 18 23:39:47 UTC 2021 up 10 days, 18:20, 0 users, load averages: 2.54, 2.36, 2.04

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.