Re: Factoring and Randomness
From: Phil Carmody (thefatphil_demunged_at_yahoo.co.uk)
Date: 10/31/04
- Next message: ben ito: "fermat"
- Previous message: mareg_at_mimosa.csv.warwick.ac.uk: "Re: Simple group(s) of order 504?"
- In reply to: R3769: "Factoring and Randomness"
- Next in thread: R3769: "Re: Factoring and Randomness"
- Reply: R3769: "Re: Factoring and Randomness"
- Messages sorted by: [ date ] [ thread ]
Date: 31 Oct 2004 23:14:33 +0200
r3769@aol.com (R3769) writes:
> Suppose p is a composite positive integer, set n[0]=1 and consider the sequence
> <n[i]> defined for i>0 as follows:
>
> n[i+1]=p-1-((p*i-1) mod n[i]).
>
> It would seem that for some i1, gcd(p,n[i])>1, whenever i>i1. I.e. factoring p
> is possibly no more difficult than computing n[i] for sufficiently large i.
> Suppose this is in fact the case. What, if anything, can be said about the
> "randomness" of <n[i]> when i<i1?
>
> Clearly, the first few n[i] are quite predictable. Otoh if there is a
> polynomial f(i) (or any other easily computed function) such that f(i) mod p
> and n[i] always agree, then factoring p is trivial (given the supposition).
> So it is reasonable to say that over some range, say i0<i<i1, <n[i]> is perhaps
> quite unpredictable, but is it "as random as factoring is difficult" ?
There's no reason why it should factor a number any more effectively
than simply taking the gcd with a random number.
Your technique takes i iterations to find the factor p of 12!+x
where i>>(p/log(p)) as follows:
i p x
75 29 13
256 97 17
222 131 31
50 19 47
67 29 71
...
Given the choice between trial division and that, I'd stick to trial division.
Phil
-- They no longer do my traditional winks tournament lunch - liver and bacon. It's just what you need during a winks tournament lunchtime to replace lost ... liver. -- Anthony Horton, 2004/08/27 at the Cambridge 'Long Vac.'
- Next message: ben ito: "fermat"
- Previous message: mareg_at_mimosa.csv.warwick.ac.uk: "Re: Simple group(s) of order 504?"
- In reply to: R3769: "Factoring and Randomness"
- Next in thread: R3769: "Re: Factoring and Randomness"
- Reply: R3769: "Re: Factoring and Randomness"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
