Re: Factoring integers on a classical computer

From: Ross A. Finlayson (raf_at_tiki-lounge.com)
Date: 03/15/05 

Date: 14 Mar 2005 21:31:13 -0800

Virgil wrote:
> In article <1110562012.608005.290220@l41g2000cwc.googlegroups.com>,
> "Craig Feinstein" <cafeinst@msn.com> wrote:
>
> > Is there any known algorithm which factors integers that has a
better
> > worst-case running-time than the brute force method (of testing all
> > integers between 1 and sqrt(n) to see if one of them divides n)?
> >
> > Note: It is known that there are methods out there which are more
> > practical than brute force, but these methods don't always work so
well
> > and when they do not work so well, they run slower than the brute
force
> > method.
> >
> > Craig
>
> One can save time by eliminating at least some non-primes as test
> factors as you go. Using only odd test factors other than 2
immediately
> cuts your time nearly in half.

That reminds me of digit summation congruence, or "DSC."

That might be useful, basically it is like "casting out nines", sum the
digits of a decimal number, if it's divisible by nine then so is the
original number.

That's where division is much slower than summing each digit and
dividing that, where the cost of division is a function of the dividend
input length. Still, it has a sum of each digit, which is a function
of the input length. So, I wonder if there is a better way to go about
that.

Basically the notion is that on a computer the test value is
represented as a bitstream or "extended precision integer", and you can
test it for divisibility by Mersenne numbers (2^n-1) by grouping the n
many bits in a digit of base 2^n. For example, to see if some number
represented in 10 million bytes (octets) is an integer multiple of
255, sum the bytes and test that for divisibility by 255. Then you'd
be testing a number less then 2550 million instead of 2^80000000 for
divisibility, by trial division. That might be useful where 1/3 if
random integers are multiples of 3, 1/7 multiples of 7, 1/15 multiples
of 15, ..., for Mersenne number factors.

It seems intuitively feasible because humans use it, it's easy to tell
that 345634563456654365436543 is an integral multiple of nine because
it's digits in base 10 sum to an integral multiple of nine. There are
many known divisibility tests, in this case base-specific
number-theoretic divisibility tests.

Still, I wonder if there's a better way than summing the values, for
example a binary operation upon them. For example 0x0303 is a multiple
of 3. Grouping that into digits of two bits for base 4: 0, 0, 0, 3, 0,
0, 0, 3. If you xor each digit, then the result is zero. Yet, 1, 2,
3, 0, you xor those together and the result is zero. 1, 2, 1, 2, same.
 Is it so that instead of having to sum the values that you could just
xor the digits together and test against zero? No, 0, 0, 0, 3. Yet,
what if xor the digits and then test for zero or the number? No: 1,
1. What if you xor each digit with 3 and then xor those results
together? No: 2, 2.

It's easy to consider lookup tables for the sums of various numbers of
octets, and other machine architecture considerations.

http://groups-beta.google.com/group/sci.math/browse_thread/thread/bc51ff338bdc1b81/

Basically: an intermediate naive method using divisibility tests for
prefiltering trial divisions based on exploitation of machine integer
representation might increase the speed of factorization for large
composites with small Mersenne number factors.

So, I guess DSC is mostly just a brute force multiplier, leverage.
Compared to the more sophisticated Fermatian and EC methods, it is
quite naive.

Ross F.

Relevant Pages

  • Re: Factoring integers on a classical computer
    ... That reminds me of digit summation congruence, ... That might be useful, basically it is like "casting out nines", sum the ... sum the bytes and test that for divisibility by 255. ... that 345634563456654365436543 is an integral multiple of nine because ...
    (sci.math)
  • Re: Test of divisibility
    ... I recently read in a book, about divisibility tests as follows ... multiply the last digit of the given number by the operator of 7(i.e ... and subtract the product from the number obtained by removing the last ... here 35 is a multiple of 7, therefore the number 3563 is divisible by ...
    (sci.math)
  • Test of divisibility
    ... I recently read in a book, about divisibility tests as follows ... multiply the last digit of the given number by the operator of 7(i.e ... and subtract the product from the number obtained by removing the last ... here 35 is a multiple of 7, therefore the number 3563 is divisible by ...
    (sci.math)
  • Re: Some maths help in a ebook
    ... multiple-digit number, sum those. ... It's a subset of the divisibility check for 9, known to accountants as "casting out nines". ... N modis the units digit minus the tens digit plus the hundreds digit minus ...
    (comp.dsp)
  • Re: Why is 12345678, 85263147, etc. always divisible by 9?
    ... Don't know the divisibility rule fby 9? ... A number is divisible by 9 iif the sum of its digits is ... If the sum of the digits is a multiple of 7, ...
    (sci.math)
Loading