Groups > comp.compression > #823 > unrolled thread

Modulus, Factoring and Compressing random data

Started by	Ernst <Ernst_Berg@sbcglobal.net>
First post	2012-01-24 09:46 -0800
Last post	2012-02-02 07:46 -0500
Articles	20 on this page of 119 — 13 participants

Back to article view | Back to comp.compression

  Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-01-24 09:46 -0800
    Re: Modulus, Factoring and Compressing random data Earl_Colby_Pottinger <earlcolby.pottinger@sympatico.ca> - 2012-01-24 13:03 -0800
      Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-01-24 14:52 -0800
        Re: Modulus, Factoring and Compressing random data jacko <jackokring@gmail.com> - 2012-01-24 15:25 -0800
          Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-01-24 16:49 -0800
            Re: Modulus, Factoring and Compressing random data Earl_Colby_Pottinger <earlcolby.pottinger@sympatico.ca> - 2012-01-24 18:55 -0800
              Re: Modulus, Factoring and Compressing random data jacko <jackokring@gmail.com> - 2012-01-24 19:23 -0800
                Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-01-24 21:08 -0800
              Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-01-24 20:50 -0800
    Re: Modulus, Factoring and Compressing random data Robert Wessel <robertwessel2@yahoo.com> - 2012-01-25 00:09 -0600
      Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-01-24 23:51 -0800
        Re: Modulus, Factoring and Compressing random data Robert Wessel <robertwessel2@yahoo.com> - 2012-01-25 02:28 -0600
          Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-01-25 02:54 -0800
          Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-01-25 03:08 -0800
        Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-01-24 23:58 -0800
      Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-01-25 00:08 -0800
      Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-01-25 02:40 -0800
        Re: Modulus, Factoring and Compressing random data Robert Wessel <robertwessel2@yahoo.com> - 2012-01-25 05:25 -0600
          Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-01-25 05:20 -0800
          Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-01-25 12:12 -0800
            Re: Modulus, Factoring and Compressing random data Earl_Colby_Pottinger <earlcolby.pottinger@sympatico.ca> - 2012-01-25 13:32 -0800
              Re: Modulus, Factoring and Compressing random data James Dow Allen <jdallen2000@yahoo.com> - 2012-01-25 14:33 -0800
                Re: Modulus, Factoring and Compressing random data Robert Wessel <robertwessel2@yahoo.com> - 2012-01-25 17:43 -0600
                  Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-01-25 19:00 -0800
                    Re: Modulus, Factoring and Compressing random data Earl_Colby_Pottinger <earlcolby.pottinger@sympatico.ca> - 2012-01-26 07:17 -0800
                  Re: Modulus, Factoring and Compressing random data David Thompson <dave.thompson2@verizon.net> - 2012-02-08 06:06 -0500
                    Re: Modulus, Factoring and Compressing random data Earl_Colby_Pottinger <earlcolby.pottinger@sympatico.ca> - 2012-02-08 07:30 -0800
              Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-01-25 15:19 -0800
    Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-01-26 02:20 -0800
      Re: Modulus, Factoring and Compressing random data Earl_Colby_Pottinger <earlcolby.pottinger@sympatico.ca> - 2012-01-26 07:25 -0800
        Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-01-26 18:52 -0800
          Re: Modulus, Factoring and Compressing random data Thomas Richter <thor@math.tu-berlin.de> - 2012-01-27 09:25 +0100
            Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-01-27 12:01 -0800
            Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-01-27 12:12 -0800
              Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-01-27 16:13 -0800
                Re: Modulus, Factoring and Compressing random data Thomas Richter <thor@math.tu-berlin.de> - 2012-01-28 11:22 +0100
                  Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-01-28 13:59 -0800
                    Re: Modulus, Factoring and Compressing random data Thomas Richter <thor@math.tu-berlin.de> - 2012-01-30 09:49 +0100
                      Re: Modulus, Factoring and Compressing random data stan <smoore@exis.net> - 2012-01-30 08:51 -0500
                        Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-01-30 08:51 -0800
                      Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-01-30 08:38 -0800
                        Re: Modulus, Factoring and Compressing random data stan <smoore@exis.net> - 2012-01-30 18:44 -0500
                          Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-01-30 15:49 -0800
                            Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-01-30 16:27 -0800
                              Re: Modulus, Factoring and Compressing random data Thomas Richter <thor@math.tu-berlin.de> - 2012-01-31 08:46 +0100
                                Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-01-31 03:58 -0800
                                  Re: Modulus, Factoring and Compressing random data Thomas Richter <thor@math.tu-berlin.de> - 2012-01-31 21:58 +0100
                            Re: Modulus, Factoring and Compressing random data stan <smoore@exis.net> - 2012-01-31 07:41 -0500
                              Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-01-31 15:27 -0800
                                Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-01-31 16:06 -0800
                                  Re: Modulus, Factoring and Compressing random data stan <smoore@exis.net> - 2012-02-01 07:47 -0500
                                    Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-02-01 09:38 -0800
                                      Re: Modulus, Factoring and Compressing random data "George Johnson" <matrix29@charter.net> - 2012-02-02 08:10 -0500
                                    Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-02-01 20:22 -0800
                                      Re: Modulus, Factoring and Compressing random data stan <smoore@exis.net> - 2012-02-02 06:31 -0500
                                        Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-02-02 14:15 -0800
                                        Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-02-02 19:18 -0800
                                          Re: Modulus, Factoring and Compressing random data "George Johnson" <matrix29@charter.net> - 2012-02-07 06:21 -0500
                                Re: Modulus, Factoring and Compressing random data stan <smoore@exis.net> - 2012-01-31 19:06 -0500
                                  Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-01-31 19:15 -0800
                                    Re: Modulus, Factoring and Compressing random data stan <smoore@exis.net> - 2012-02-01 08:24 -0500
                                      Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-02-01 09:54 -0800
                                      Re: Modulus, Factoring and Compressing random data Jim Leonard <mobygamer@gmail.com> - 2012-02-01 11:00 -0800
                                        Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-02-01 21:19 -0800
                                          Re: Modulus, Factoring and Compressing random data Jim Leonard <mobygamer@gmail.com> - 2012-02-02 07:15 -0800
                                      Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-02-01 20:25 -0800
                                        Re: Modulus, Factoring and Compressing random data stan <smoore@exis.net> - 2012-02-02 07:07 -0500
                                          Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-02-02 19:35 -0800
                                            Re: Modulus, Factoring and Compressing random data "George Johnson" <matrix29@charter.net> - 2012-02-07 06:33 -0500
                                  Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-01-31 18:51 -0800
                                    Re: Modulus, Factoring and Compressing random data Sebastian <s.gesemann@gmail.com> - 2012-02-01 03:51 -0800
                                      Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-02-01 09:34 -0800
                                    Re: Modulus, Factoring and Compressing random data stan <smoore@exis.net> - 2012-02-01 08:53 -0500
                                      Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-02-01 20:31 -0800
                                        Re: Modulus, Factoring and Compressing random data stan <smoore@exis.net> - 2012-02-02 07:18 -0500
                          Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-01-30 16:47 -0800
                            Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-01-30 17:00 -0800
                              Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-01-30 18:55 -0800
                            Re: Modulus, Factoring and Compressing random data stan <smoore@exis.net> - 2012-01-31 08:10 -0500
                              Re: Modulus, Factoring and Compressing random data Earl_Colby_Pottinger <earlcolby.pottinger@sympatico.ca> - 2012-01-31 11:31 -0800
                                Re: Modulus, Factoring and Compressing random data Noob <root@127.0.0.1> - 2012-02-02 11:11 +0100
                                  Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-02-02 14:05 -0800
                                    Re: Modulus, Factoring and Compressing random data stan <smoore@exis.net> - 2012-02-08 13:35 -0500
                                Re: Modulus, Factoring and Compressing random data Noob <root@127.0.0.1> - 2012-02-02 11:24 +0100
                                  Re: Modulus, Factoring and Compressing random data Noob <root@127.0.0.1> - 2012-02-02 12:52 +0100
                                  Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-02-02 14:06 -0800
                    Re: Modulus, Factoring and Compressing random data Sebastian <s.gesemann@gmail.com> - 2012-01-30 07:09 -0800
                      Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-01-30 07:45 -0800
                        Re: Modulus, Factoring and Compressing random data Sebastian <s.gesemann@gmail.com> - 2012-01-30 09:42 -0800
                          Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-01-30 10:19 -0800
                          Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-01-30 12:05 -0800
                            Re: Modulus, Factoring and Compressing random data Jim Leonard <mobygamer@gmail.com> - 2012-01-30 14:40 -0800
                              Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-01-30 15:11 -0800
                                Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-01-30 15:43 -0800
                              Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-01-30 14:52 -0800
                            Re: Modulus, Factoring and Compressing random data Sebastian <s.gesemann@gmail.com> - 2012-01-31 04:31 -0800
                              Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-01-31 14:21 -0800
                                Re: Modulus, Factoring and Compressing random data pfraser <pete_fraser@comcast.net> - 2012-01-31 15:04 -0800
                                  Re: Modulus, Factoring and Compressing random data Noob <root@127.0.0.1> - 2012-02-01 10:50 +0100
                                    Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-02-01 20:19 -0800
                              Re: Modulus, Factoring and Compressing random data jacko <jackokring@gmail.com> - 2012-02-02 00:51 -0800
                                Re: Modulus, Factoring and Compressing random data Thomas Richter <thor@math.tu-berlin.de> - 2012-02-02 10:09 +0100
                                  Re: Modulus, Factoring and Compressing random data jacko <jackokring@gmail.com> - 2012-02-02 11:43 -0800
                                    Re: Modulus, Factoring and Compressing random data Sebastian <s.gesemann@gmail.com> - 2012-02-03 01:21 -0800
                                      Re: Modulus, Factoring and Compressing random data Sebastian <s.gesemann@gmail.com> - 2012-02-03 02:43 -0800
                                        Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-02-04 15:42 -0800
                                  Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-02-02 13:53 -0800
                                    Re: Modulus, Factoring and Compressing random data stan <smoore@exis.net> - 2012-02-08 13:32 -0500
                                Re: Modulus, Factoring and Compressing random data Sebastian <s.gesemann@gmail.com> - 2012-02-02 01:56 -0800
                                  Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-02-02 13:54 -0800
                                Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-02-02 12:59 -0800
                                Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-02-02 12:47 -0800
                                  Re: Modulus, Factoring and Compressing random data Ernst <Ernst_Berg@sbcglobal.net> - 2012-02-02 23:54 -0800
                                    Re: Modulus, Factoring and Compressing random data stan <smoore@exis.net> - 2012-02-08 13:22 -0500
                                  Re: Modulus, Factoring and Compressing random data Earl_Colby_Pottinger <earlcolby.pottinger@sympatico.ca> - 2012-02-04 20:45 -0800
            Re: Modulus, Factoring and Compressing random data Noob <root@127.0.0.1> - 2012-01-30 15:32 +0100
    Re: Modulus, Factoring and Compressing random data "George Johnson" <matrix29@charter.net> - 2012-02-02 06:34 -0500
    Re: Modulus, Factoring and Compressing random data "George Johnson" <matrix29@charter.net> - 2012-02-02 07:29 -0500
    Re: Modulus, Factoring and Compressing random data "George Johnson" <matrix29@charter.net> - 2012-02-02 07:46 -0500

Page 2 of 6 — ← Prev page 1 [2] 3 4 5 6 Next page →

#851

From	Earl_Colby_Pottinger <earlcolby.pottinger@sympatico.ca>
Date	2012-01-25 13:32 -0800
Message-ID	<ffca506d-49a7-45e7-8dd3-a1e80a34fd0d@t8g2000yqg.googlegroups.com>
In reply to	#850

On Jan 25, 3:12 pm, Ernst <Ernst_B...@sbcglobal.net> wrote:

>  I need to check the software over again and write a version that can
> factor million digit file.

Can I assume you are using the numbers shown in http://en.wikipedia.org/wiki/RSA_numbers
?

Since the answers are given for some of the simpler number it will
make for a quick confirmation that your program is working properly.

And of you really want to wow the people here, factor one of the
unsolved numbers.

[toc] | [prev] | [next] | [standalone]

#852

From	James Dow Allen <jdallen2000@yahoo.com>
Date	2012-01-25 14:33 -0800
Message-ID	<fd21a710-8f67-43c9-8cac-b8b8df67c9e2@pk8g2000pbb.googlegroups.com>
In reply to	#851

On Jan 26, 4:32 am, Earl_Colby_Pottinger
<earlcolby.pottin...@sympatico.ca> wrote:

> ... assume you are using the numbers shown inhttp://en.wikipedia.org/wiki/RSA_numbers
> ? ...
>
> And [i]f you really want to wow the people here, factor one of the
> unsolved numbers.

The article does state that some numbers have not
been factored, but may I assume that anyone with
access to (secret?) RSA Lab records would know the
two factors?

[toc] | [prev] | [next] | [standalone]

#854

From	Robert Wessel <robertwessel2@yahoo.com>
Date	2012-01-25 17:43 -0600
Message-ID	<tn41i7hobo21ihb19lt6pqhas4v6emj53r@4ax.com>
In reply to	#852

On Wed, 25 Jan 2012 14:33:59 -0800 (PST), James Dow Allen
<jdallen2000@yahoo.com> wrote:

>On Jan 26, 4:32 am, Earl_Colby_Pottinger
><earlcolby.pottin...@sympatico.ca> wrote:
>
>> ... assume you are using the numbers shown inhttp://en.wikipedia.org/wiki/RSA_numbers
>> ? ...
>>
>> And [i]f you really want to wow the people here, factor one of the
>> unsolved numbers.
>
>The article does state that some numbers have not
>been factored, but may I assume that anyone with
>access to (secret?) RSA Lab records would know the
>two factors?

Why would you assume that?  It's possible, but why keep that
information, especially if you're going to offer cash prizes for
factoring?  Having the answers would just encourage bad behavior.  And
once somebody proposes an answer, checking it is trivial.

Consider that no one keeps the primes that go into generating a RSA
key pair either.

[toc] | [prev] | [next] | [standalone]

#858

From	Ernst <Ernst_Berg@sbcglobal.net>
Date	2012-01-25 19:00 -0800
Message-ID	<807aea66-adb7-4801-96ed-0cd473ad1629@ih8g2000pbc.googlegroups.com>
In reply to	#854

On Jan 25, 3:43 pm, Robert Wessel <robertwess...@yahoo.com> wrote:
> On Wed, 25 Jan 2012 14:33:59 -0800 (PST), James Dow Allen
>

Just tagging on to the end Robert.  Pardon the reply to your
conversation with James.

 Update guys..  Yes I had a flaw in the code.   You see as it was
written I was testing a previous state and if the number at6 the start
of the cycle is a factor no previous state exists yet the residual
state from the previous cycle was telling it this was a sequence that
ended in 1,0 not Factor,0.

 I just ran RSA576 and increased "factor" from an ending of 3317 to
4000 so it would run a bit before it found an answer. It stopped on
que.

  if anyone wants a print out of sequences for RSA576 I can do that. I
would post sequence here except it's a lot of text.

 Okay I can start again. I am open to suggestions for intelligent
picks of M in N mod M oh and previous print outs states "For N" but it
should have been "For M" in case any one is confused by my printout
and N mod M  I will refer to RM as N mod M

 Robert have you written any code with RM in it?  I kinda got the
feeling you had written a few lines yesterday.
I am unsure if this will be brute force of if a factor will show for
"large prime x prime" If the functioning holds for large as well as
small then it would show up in sequence rather than as a starting
value for a cycle.

Alright.. It's still fun today but what will I do tomorrow?

Ernst

[toc] | [prev] | [next] | [standalone]

#861

From	Earl_Colby_Pottinger <earlcolby.pottinger@sympatico.ca>
Date	2012-01-26 07:17 -0800
Message-ID	<0bd4ca0d-2e49-49dc-9349-334121ec064a@k28g2000yqn.googlegroups.com>
In reply to	#858

On Jan 25, 10:00 pm, Ernst <Ernst_B...@sbcglobal.net> wrote:

>  I just ran RSA576 and increased "factor" from an ending of 3317 to
> 4000 so it would run a bit before it found an answer. It stopped on
> que.
>
>   if anyone wants a print out of sequences for RSA576 I can do that. I
> would post sequence here except it's a lot of text.

What the heck are you talking about?  It is only two numbers!

See http://www.rsa.com/rsalabs/node.asp?id=2096 for them.  Now how
about doing a RSA that was not solved?   You just have to supply the
two factors, then anyone can test if you have something by multipling
the two numbers.  It is a easy test that could be done with paper and
pencil if needed.

[toc] | [prev] | [next] | [standalone]

#1000

From	David Thompson <dave.thompson2@verizon.net>
Date	2012-02-08 06:06 -0500
Message-ID	<fol4j7dekoheqoa0d9pv2niab460i1pmq9@4ax.com>
In reply to	#854

On Wed, 25 Jan 2012 17:43:32 -0600, Robert Wessel
<robertwessel2@yahoo.com> wrote:

> On Wed, 25 Jan 2012 14:33:59 -0800 (PST), James Dow Allen
> <jdallen2000@yahoo.com> wrote:

> >> http://en.wikipedia.org/wiki/RSA_numbers

> >The article does state that some numbers have not
> >been factored, but may I assume that anyone with
> >access to (secret?) RSA Lab records would know the
> >two factors?
> 
> 
> Why would you assume that?  It's possible, but why keep that
> information, especially if you're going to offer cash prizes for
> factoring?  Having the answers would just encourage bad behavior.  And
> once somebody proposes an answer, checking it is trivial.
> 
For this unusual purpose (a factoring challenge), perhaps.

> Consider that no one keeps the primes that go into generating a RSA
> key pair either.

But not in the normal usage case. Most implementations of RSA since
the earliest days use the much more efficient Chinese Remainder
Theorem aka CRT method for privatekey operations. The CRT-form
privatekey retains p and q, plus reduced exponents and a coefficient.
See PKCS#1 on the RSA (or maybe now EMC) website, or in possibly more
reliably available form RFCs 2313 2347 3447. (The publickey of course
must not include this information, but publickey operations don't need
the performance improvement provided by CRT -- fortunately.)

And besides the naive privatekey (d, n) combined with the public
exponent e is sufficient to factor n, so it doesn't matter whether you
store the factors or not as long as the key is active.

I don't know what RSA Labs actually did. They could have simply
generated the semiprimes and discarded the factors. OTOH the generally
accepted best practice for key management, especially back then when
RSA as the first practical public-key algorithm was struggling to
displace established symmetric-encryption key-management schemes,
is/was to generate private (or secret) keys in secure hardware with
"dual control" requiring input or authorization from two (or more)
different people, so that no one person can compromise it. That
procedure also would have worked for challenge numbers.

[toc] | [prev] | [next] | [standalone]

#1006

From	Earl_Colby_Pottinger <earlcolby.pottinger@sympatico.ca>
Date	2012-02-08 07:30 -0800
Message-ID	<d9f360cf-3345-44e5-9e4a-53f429b24756@t15g2000yqi.googlegroups.com>
In reply to	#1000

Who cares!

Ernst is the one claiming to be able to factor RSA numbers, let him do
it to prove his claim!

The fact that he still has not done so suggests he can not. And that
ability is not affected no matter how many people at the RSA labs may
have the secret primes.

[toc] | [prev] | [next] | [standalone]

#853

From	Ernst <Ernst_Berg@sbcglobal.net>
Date	2012-01-25 15:19 -0800
Message-ID	<47500030-60d7-4307-9b1d-a998e7bcfa23@4g2000pbz.googlegroups.com>
In reply to	#851

On Jan 25, 1:32 pm, Earl_Colby_Pottinger
<earlcolby.pottin...@sympatico.ca> wrote:
> On Jan 25, 3:12 pm, Ernst <Ernst_B...@sbcglobal.net> wrote:
>
> >  I need to check the software over again and write a version that can
> > factor million digit file.
>
> Can I assume you are using the numbers shown inhttp://en.wikipedia.org/wiki/RSA_numbers
> ?
>
> Since the answers are given for some of the simpler number it will
> make for a quick confirmation that your program is working properly.
>
> And of you really want to wow the people here, factor one of the
> unsolved numbers.

Well this is a learning phase.  I came here and asked first.

 That is an excellent idea on the smaller factored RSA's  I ran some
of the 64 bit numbers and found the same data of factors using the GMP
version.

I have to admit I have not had time today to check the program over
again.

 I will make time tonight.

Just to remind folks.  This is an exploration into what Recursive
modulus is and what it does and doesn't do.  I made the discovery
three days ago and I thought I was simply rediscovering old news.

What it seems to do at least for 64 bit values is exit the recursive
modulus, ie become a zero result, and if the previous value was
greater than 1 there is a factor.

Now Robert suggested that this approach suffers the same fate as other
efforts when it comes to large primes such as RSA2048 and that may
well be true.
I'll have more to say on the utility of what I cobbled together
yesterday and admit I have not tested well enough.

Here is the basic idea for those who are following what I do and want
more information.

z = 4295229443u;

for(x=z-1; x > 1; x-- )
{
y = z % x; prev = y;
for(;;){ if( y>0 ){ y = z % prev; if(y>0)prev = y;} else break; }
if( y == 0 & prev > 1 ) {    printf("Factor found %lu for N of  %lu
\n",prev,x); }

}

Z is the number we are looking for a factor of, our  N of N mod M
Not knowing what is best for M I simply scale N and it's okay for
small numbers but the search time for really large numbers .. well
there in is what Robert is referencing I believe.

 The use the already factored RSA's is an excellent suggestion for
debugging.  I'll get on it in a few hours.

This is what it is but I smile at the thought of wow-ing our friends.

Again I'll have time to work later tonight.  This isn't that
complicated but that doesn't mean I have a flaw in my GMP code when
the non-GMP code worked right.

[toc] | [prev] | [next] | [standalone]

#859

From	Ernst <Ernst_Berg@sbcglobal.net>
Date	2012-01-26 02:20 -0800
Message-ID	<21290873.828.1327573218668.JavaMail.geo-discussion-forums@prdv33>
In reply to	#823

 I was just thinking that if RSA2048 is prime then if I multiply it by a prime I should see only it and the prime I multiplied against in the stream.

Does that sound reasonable?

[toc] | [prev] | [next] | [standalone]

#862

From	Earl_Colby_Pottinger <earlcolby.pottinger@sympatico.ca>
Date	2012-01-26 07:25 -0800
Message-ID	<9505b21a-5fe4-4bae-8f9c-4b92b54bfc69@f11g2000yql.googlegroups.com>
In reply to	#859

On Jan 26, 5:20 am, Ernst <Ernst_B...@sbcglobal.net> wrote:
>  I was just thinking that if RSA2048 is prime then if I multiply it by a prime I should see only it and the prime I multiplied against in the stream.
>
> Does that sound reasonable?

No it is NOT reasonable!

All, repeat ALL the RSA numbers are the result of multiplying TWO very
large prime numbers! That is it!  There is no larger sequence of
numbers if you factor a RSA number, there is not any RSA numbers that
are prime numbers. They are all multiples of two large primes only.

So when are you going to try you code on something hard?

[toc] | [prev] | [next] | [standalone]

#863

From	Ernst <Ernst_Berg@sbcglobal.net>
Date	2012-01-26 18:52 -0800
Message-ID	<20086931.544.1327632761300.JavaMail.geo-discussion-forums@prlv30>
In reply to	#862

Earl,

  I understand that may well be the case but I don't know and unless you worked on that project you don't "KNOW" for sure.

 So I'm open minded about it until I do know.  That's all.  It's innocent enough friend.

 You ask when am I to try on something hard?  Well, Earl from what I can tell there is no difference in factoring RSA2048 ( which I have three processors searching right now actually ) and say Million Digit file.

 Now I need to sit down and write the version that will factor million digit but it's trivial.
 Now the forum and you my friends are fond of the put up or shut up on data compression so please note I put up already.
 We can skip the traditional shut-ups from here on out.  Okay?

Now, Earl, if there is something about recursive modulus I can explain I'll try.  Just ask. 
 How did you like the code segment I posted.  Tight loop huh?  I like that one myself.

 As for coding?  I have stopped work on my previous effort and will jump on the factoring band wagon.
 Did you want to work with me on it?

Ernst

[toc] | [prev] | [next] | [standalone]

#864

From	Thomas Richter <thor@math.tu-berlin.de>
Date	2012-01-27 09:25 +0100
Message-ID	<jftn2b$acu$1@news.belwue.de>
In reply to	#863

Am 27.01.2012 03:52, schrieb Ernst:
> Earl,
>
>    I understand that may well be the case but I don't know and unless you worked on that project you don't "KNOW" for sure.

Of course he *knows* for sure. That's the whole point of how RSA works. 
It is defined this way.

Factoring by modulus is actually an ancient method, and not a very good 
one either, nor a modern one. If you want to have better tests for 
prime-testing, look for example for "Factoring by Fermat's method", or 
"Factoring by Phi-Method". You find this in Donald Knuth's "The Art of 
Programming, Volume 2", for example. It is not hard to implement them,
and they are considerably faster than this.

[toc] | [prev] | [next] | [standalone]

#865

From	Ernst <Ernst_Berg@sbcglobal.net>
Date	2012-01-27 12:01 -0800
Message-ID	<30508524.21.1327694475057.JavaMail.geo-discussion-forums@preh38>
In reply to	#864

Well picking nits is the foundation of arguments..  

From my point of view I will be experiencing these "factorings" with an open mind is all.

 Thank you for the "links."

 Ah, but they are not this.

 Ernst

[toc] | [prev] | [next] | [standalone]

#866

From	Ernst <Ernst_Berg@sbcglobal.net>
Date	2012-01-27 12:12 -0800
Message-ID	<25445276.18.1327695177390.JavaMail.geo-discussion-forums@prez15>
In reply to	#864

Oh Tom,

 I mentioned that modulus is related as such in what the first post.

But cool that you stopped by if for nothing else but to criticize. 
Par for the Comp.Compression course I am afraid but still you bothered.

Thanks

[toc] | [prev] | [next] | [standalone]

#867

From	Ernst <Ernst_Berg@sbcglobal.net>
Date	2012-01-27 16:13 -0800
Message-ID	<16309604.72.1327709609752.JavaMail.geo-discussion-forums@prmu37>
In reply to	#866

Okay Friends..

 I am comfortable with the recursive modulus. 

For better or worse there it is.

I'd like to know if this has already been discovered or not so I can make the proper statements about recursive modulus in the future.

I welcome email as to the truth of who, what and when of the discovery of recursive modulus and factoring.
 I understand and have stated that modulus has been and continues to be a tool in factoring numbers.

 Also friends realize I came to ask the question innocently enough since, ahem, you guys are my smart friends even if we fight like cats and dogs.

 Thanks for everyone's time in reading and replying.
 I do have a lot of learning to do about factoring but I am used to diving in the deep end to learn to swim so to speak.

Ernst

[toc] | [prev] | [next] | [standalone]

#871

From	Thomas Richter <thor@math.tu-berlin.de>
Date	2012-01-28 11:22 +0100
Message-ID	<jg0i9g$a77$1@news.belwue.de>
In reply to	#867

On 28.01.2012 01:13, Ernst wrote:
> Okay Friends..
>
>   I am comfortable with the recursive modulus.
>
> For better or worse there it is.
>
> I'd like to know if this has already been discovered or not

It has. Did you read my post above? Actually, one of its applications is 
that Euler showed 1732 (yes, it is that ancient) that the Fermat number 
F_5 is divisible by 641 (and hence not prime).

[toc] | [prev] | [next] | [standalone]

#876

From	Ernst <Ernst_Berg@sbcglobal.net>
Date	2012-01-28 13:59 -0800
Message-ID	<1309622.345.1327787969010.JavaMail.geo-discussion-forums@prdh15>
In reply to	#871

Is it the one where the number is subtracted by one each time?
Would you be so kind as to link-me to the example because I didn't find a reference I could identify when I looked last.

I figure that modulus has been used but I didn't see use of using the remainder over and over until the answer is zero and if the number before is greater than 1 it is a factor.

 It's cool if I rediscovered because I actually am trying to do something different than factor.  However now that I see how simple this is I am exploring factoring.

So if this has been known forever why then have none of you found at least the first three factors of Million Digit file?
 I'm the uneducated one here.

Please link me.  I really didn't see or understand then.


Ernst

[toc] | [prev] | [next] | [standalone]

#878

From	Thomas Richter <thor@math.tu-berlin.de>
Date	2012-01-30 09:49 +0100
Message-ID	<jg5lje$4uj$1@news.belwue.de>
In reply to	#876

Am 28.01.2012 22:59, schrieb Ernst:
> Is it the one where the number is subtracted by one each time?

This is one particular way how a remainder can be computed,though not 
the most efficient.

> Would you be so kind as to link-me to the example because I didn't find a reference I could identify when I looked last.

Link? I provided a *book*. You know, these things on paper, find them in 
libraries? Old-school information carrier? Actually, for the classical 
GCD algorithm, the first volume of Knuth contains quite an extensive 
study, but for modulus in general, and for Eulers work, any introductory 
book on algebra (*not* linear algebra) would suffice. Look in particular 
for the words "Number Rings", because this is what is all behind this.

> So if this has been known forever why then have none of you found at least the first three factors of Million Digit file?

Because nobody cared? What would you do with the first factors of the 
file in first place? Or what makes you believe that they can be 
reppresented in a more compact way than the number itself?

As stated, for finding factors, there are quite a couple of algorithms, 
as stated in Knuth's book, but for numbers that size you need at least 
support for "large integers" (GNU BigNum (sp?) comes to my mind), and 
probably algorithms more advanced than the ones I quoted, and certainly 
a lot more advanced than a simple modulus reduction.

> Please link me.  I really didn't see or understand then.

What you need is not a link. It is a course on algebra. You cannot just 
learn this from a web page, you need to invest some time of yours. Maybe 
a book can help.

http://en.wikipedia.org/wiki/Ring_of_integers
http://en.wikipedia.org/wiki/Algebraic_field

contains a very rough introduction, but essentially, the remainders 
after division form a mathematical object called "commutative ring", 
which means that you can add, subtract and multiply (but not necessarily 
divide) within. The properties of the modulus operation, especially how 
to split a number into factors by this method then follows from the 
properties of these rings.

http://en.wikipedia.org/wiki/Modular_arithmetic

lists some of them.

[toc] | [prev] | [next] | [standalone]

#879

From	stan <smoore@exis.net>
Date	2012-01-30 08:51 -0500
Message-ID	<7rjiv8-2k6.ln1@invalid.net>
In reply to	#878

Thomas Richter wrote:
> Am 28.01.2012 22:59, schrieb Ernst:
<snip>
>> Would you be so kind as to link-me to the example because I didn't
>> find a reference I could identify when I looked last.
>
> Link? I provided a *book*. You know, these things on paper, find them in 
> libraries? Old-school information carrier? Actually, for the classical 
> GCD algorithm, the first volume of Knuth contains quite an extensive 
> study, but for modulus in general, and for Eulers work, any introductory 
> book on algebra (*not* linear algebra) would suffice. Look in particular 
> for the words "Number Rings", because this is what is all behind
> this.

You might want to look for Discrete math books, we covered quite a bit
of modulus information and did many exercises/proofs. The area is very
well studied and pretty well known.

>> So if this has been known forever why then have none of you found
>> at least the first three factors of Million Digit file?

It's not a good way to factor. As for factors and compression you
might as well count the number of vowels in the filename, they are
approximately equal in relevance. 

Put another way, if I give you the factors of the file what do you
intend to do?

[toc] | [prev] | [next] | [standalone]

#884

From	Ernst <Ernst_Berg@sbcglobal.net>
Date	2012-01-30 08:51 -0800
Message-ID	<e19c0460-d688-45b2-b560-88b4559fa380@i10g2000pbl.googlegroups.com>
In reply to	#879

On Jan 30, 5:51 am, stan <smo...@exis.net> wrote:
> Thomas Richter wrote:
> > Am 28.01.2012 22:59, schrieb Ernst:
> <snip>
> >> Would you be so kind as to link-me to the example because I didn't
> >> find a reference I could identify when I looked last.
>
> > Link? I provided a *book*. You know, these things on paper, find them in
> > libraries? Old-school information carrier? Actually, for the classical
> > GCD algorithm, the first volume of Knuth contains quite an extensive
> > study, but for modulus in general, and for Eulers work, any introductory
> > book on algebra (*not* linear algebra) would suffice. Look in particular
> > for the words "Number Rings", because this is what is all behind
> > this.
>
> You might want to look for Discrete math books, we covered quite a bit
> of modulus information and did many exercises/proofs. The area is very
> well studied and pretty well known.
>
> >> So if this has been known forever why then have none of you found
> >> at least the first three factors of Million Digit file?
>
> It's not a good way to factor. As for factors and compression you
> might as well count the number of vowels in the filename, they are
> approximately equal in relevance.
>
> Put another way, if I give you the factors of the file what do you
> intend to do?

It is what it is..  I just want to not claim discovery if I did not
discover this method.
 So the question is still on the floor.

Thank you for replying. Thank you for the input on methodologies.

 I am giving factoring some thought.  I understand that no one
methodology solves every problem.  Much like no one man knows
everything.

 So, Guys..  I am not debating the utility of modulus in data
compression.  I am not going to digest the theory behind modulus like
a scholar. I am a man who is looking to understand how to use this in
practical ways.  Also I don't want to tell people I discovered this
method when I didn't.

 Fair?

Ernst

[toc] | [prev] | [next] | [standalone]

Page 2 of 6 — ← Prev page 1 [2] 3 4 5 6 Next page →

csiph-web

Modulus, Factoring and Compressing random data

Contents

#851

#852

#854

#858

#861

#1000

#1006

#853

#859

#862

#863

#864

#865

#866

#867

#871

#876

#878

#879

#884