Re: JSH: Not obvious? Simple math test.
- From: rossum <rossum48@xxxxxxxxxxxx>
- Date: Thu, 10 Jan 2008 22:08:05 +0000
On Wed, 9 Jan 2008 07:38:57 -0800 (PST), JSH <jstevh@xxxxxxxxx> wrote:
It has finally occurred to me that some of you may not understand what[snip]
I thought was a basic math point, so this post is to check, with a
simple math test:
JSH - January 2008 Factoring method
James Harris
James has given three equations:
z^2 = y^2 + nT (1)
z = (2a)^(-1) * (1 + 2a^2)k mod p (2)
k^2 = ((a^2)+1)^(-1) * (nT) mod p (3)
From these, together with hints and examples in his blog(http://mymath.blogspot.com/) I have tried to devise a factoring
algorithm.
Given a T to factor:
1 Set n <- 1
2 Pick a prime p > sqrt(nT)
3 Set alpha <- 1 (alpha = a in the equations above)
4 Using (3) determine a value for k. This may not be possible if the
RHS of (3) is not a quadratic residue. If so then increment alpha by
1 and repeat this step.
5 Using (2) determine a value for z.
6 Using (1) determine a value for y. If y is not an integer then
increment alpha by one and return to step 4.
7 Try gcd(z+y, T), gcd(z-y, T), gcd(z+y-p, T), gcd(z-y-p, T) to see
if a factor of T is found. If a factor is found then return it and
exit, if not then increment alpha by one and return to step 4.
8 When enough values of alpha have failed, then increment n by 1.
9 If n mod 3 = 0, then increment n by 1. (n % 3 != 0)
10 Go to step 2.
Questions for James:
1 Is this a correct description of your current method?
2 Am I correct to start with n = 1 and alpha = 1?
3 How many values of alpha should I try before giving up and going on
to the next value of n?
4 When I increase n am I correct to change p so it is > sqrt(nT) or
should I leave it at its original value?
rossum
.
- Follow-Ups:
- Re: JSH: Not obvious? Simple math test.
- From: JSH
- Re: JSH: Not obvious? Simple math test.
- References:
- JSH: Not obvious? Simple math test.
- From: JSH
- JSH: Not obvious? Simple math test.
- Prev by Date: Re: JSH: Notifications continuing
- Next by Date: Re: JSH: Not obvious? Simple math test.
- Previous by thread: Re: JSH: Not obvious? Simple math test.
- Next by thread: Re: JSH: Not obvious? Simple math test.
- Index(es):
Relevant Pages
|
