Re: Congruence based factoring algorithm

On Nov 29, 3:57 pm, Patricia Shanahan <p...@xxxxxxx> wrote:
JSH wrote:
On Nov 29, 1:26 pm, Patricia Shanahan <p...@xxxxxxx> wrote:
rossum wrote:
On Sat, 29 Nov 2008 08:34:56 -0800 (PST), JSH <jst...@xxxxxxxxx>
wrote:
With all positive integers, given a target composite T to be factored,
first find a prime number p near to, or less than sqrt(T). Then pick k
such that k = p-1. Make sure k is coprime to T.
If k is not coprime to T then you have a possible factorisation; if 1
< GCD(k, T) < T then GCD(k, T) is a factor of T and the problem is
solved.  I remember that you have mentioned this in another
presentation of your algorithm, but you seem to have missed it out in
in this version.  It is also not mentioned in the latest (29 November)
version on your blog.
It would also be useful if you could qualify "near to" a bit more
accurately.  How far away from sqrt(T) can p get?  Obviously the
algorithm will run faster with as small a p as possible; what is the
lower limit on p?  As Patricia says, is p = 3 allowed for all T?
So the first few steps are:

If T is 1 then
   report that T is 1
else if T is in {2,3,5,7} then
   report that T is prime
else if T is in {4,6,8,9} then
   report a factorization of T
else
   Pick a suitable prime, p. ****
   Compute g = GCD(T,p-1)
   If g is not 1 then
     Report (g,T/g) as a factorization of T
   else
     [proceed with the rest of the algorithm]

If any prime less than sqrt(T) is suitable then the **** step is
trivial. We just pick p=3, and the GCD test becomes an evenness test.. If
not, the **** step cost depends on the exact rules for suitability.

Patricia

The only qualification on the prime p is that it be larger than the
smaller factor, assuming a product of two primes, or the smallest
factor you wish to find for a non-trivial factorization.

Previously I said that p should be greater than sqrt(T) to guarantee
that possibility but a poster found a special case where that lead to
problems, so I wanted a lesser qualification.

I now believe what he found was a very special case that has to do
with using small numbers and that in general p > sqrt(T) is ok.

Can you prove an upper bound on the numbers for which the effect can
happen? Without that proof, I would be very troubled by assuming it is a
small number effect. If that were allowed, any finite counter-example to
any proposed algorithm could be discounted as being a small number effect..



If that helps things move forward change the qualification to any p
greater than sqrt(T).

So the reason for the size of p is quite rational: p needs to be
greater than f_1, when f_1*f_2 = nT.

If your factor were 2 then p=3 would be ok.

The change from "less than sqrt(T)" to "greater than at least one factor
of T" is quite a big change. So now the **** step amounts to finding a
prime p that is greater than sqrt(T), the only way to be sure it is
greater than at least one factor of T for arbitrary T. How should that
be done, and can we bound that to polynomial time?

Patricia

Sorry but a poster on one of the math newsgroups pointed out that my
equations mean that

nT - k^2 = f_1^2 mod p

so it's equivalent to a brute force technique as a k that works gives
you f_1^2 mod p.

You get that using nT - (1+a^2)k^2 = 0 mod p and f_1 = ak mod p, which
is just something I hadn't done at this point.

So the algorithm can just be dropped as useless. Turns out it's a
brute force technique.


James Harris
.

Relevant Pages

  • Re: Project help
    ... Low Power AES algorithm using VHDL ... in GALIOS FIELD and other parts of the algorithm like galios field ...   port( ...
    (comp.lang.vhdl)
  • Re: Lockfree flqueue and lockfree_mpmc ...
    ... and they all have the same problem under contention, ... MOV ECX, EAX ... there is a problem with this algorithm on the push and pop side... ...   then ...
    (comp.programming.threads)
  • Re: Project help
    ... Low Power AES algorithm using VHDL ... in GALIOS FIELD and other parts of the algorithm like galios field ...   port( ...
    (comp.lang.vhdl)
  • Re: Searching substrings in records.
    ...     for each text field in the record ... but I just can't tell the difference between the algorithm ... you introduced above and the brute force approach I described on the ... every record and perform a substring search on any of them. ...
    (comp.programming)
  • Re: Godel proved maths inconsistent not incompleteness theorem
    ... | equals that line. ... |   a. ... your algorithm doesn't show that, for each line of the proof, ... It's not even a proof verifier for valid proofs. ...
    (sci.logic)