Prev: Considering discrete logs
Next: How Can ZFC/PA do much of Math - it Can't Even Prove PAisConsistent (EASY PROOF)
From: JSH on 29 Jun 2010 23:35
Intriguingly enough my research results studying the simple system of:

f_1 = a_1*k mod N thru f_m = a_m*k mod N

indicate that integer factorization IS itself the key to modular
arithmetic, so what I called surrogate factoring is in retrospect the
way modular arithmetic operates.

The result I recently posted showing a way to solve discrete
logarithms is amazing for its compactness but also for what it may
indicate about the power of knowledge: not knowing how modular
arithmetic works at a deep level, certain things that may be easy,
appear hard.

That result actually may eliminate the value of a large m, with k^m =
q mod N, allowing one to easily handle it by simply cancelling out
much of m with a simple technique equivalent to having a certain
number of the a's equal to k^{-1} mod N.

I'll be looking at replies with interest. One of the problems with
knowledge is when people reject it because, well, because they don't
like it!!!

That creates huge problems on a world-wide scale.

Quite simply, people refuse solutions to problems, bad things happen,
people get upset, but, they refuse solutions to problems!

It's a HUGE issue. So far the problem has been intractable.

Human beings seem to love misery. I'm not sure why. But make no
mistake, the human animal often works very hard to NOT solve its
problems, preferring often instead to whine about them, but refusing
to solve them.

That may be built into the human genome. The reasons are complex.


James Harris
From: amzoti on 30 Jun 2010 00:44
On Jun 29, 8:35 pm, JSH <jst...(a)gmail.com> wrote:
> I'll be looking at replies with interest.  One of the problems with
> knowledge is when people reject it because, well, because they don't
> like it!!!
>
> James Harris

You've been doing it for 15 years!

Great point!
From: MichaelW on 30 Jun 2010 00:50
On Jun 30, 1:35 pm, JSH <jst...(a)gmail.com> wrote:
> Intriguingly enough my research results studying the simple system of:
>
> f_1 = a_1*k mod N thru f_m = a_m*k mod N
>
> indicate that integer factorization IS itself the key to modular
> arithmetic, so what I called surrogate factoring is in retrospect the
> way modular arithmetic operates.
>
> The result I recently posted showing a way to solve discrete
> logarithms is amazing for its compactness but also for what it may
> indicate about the power of knowledge: not knowing how modular
> arithmetic works at a deep level, certain things that may be easy,
> appear hard.
>
> That result actually may eliminate the value of a large m, with k^m =
> q mod N, allowing one to easily handle it by simply cancelling out
> much of m with a simple technique equivalent to having a certain
> number of the a's equal to k^{-1} mod N.
>
> I'll be looking at replies with interest.  One of the problems with
> knowledge is when people reject it because, well, because they don't
> like it!!!
>
> That creates huge problems on a world-wide scale.
>
> Quite simply, people refuse solutions to problems, bad things happen,
> people get upset, but, they refuse solutions to problems!
>
> It's a HUGE issue.  So far the problem has been intractable.
>
> Human beings seem to love misery.  I'm not sure why.  But make no
> mistake, the human animal often works very hard to NOT solve its
> problems, preferring often instead to whine about them, but refusing
> to solve them.
>
> That may be built into the human genome.  The reasons are complex.
>
> James Harris

Find m where 2^m = 35 mod 97

T = 35^2 mod 97 = 61 mod 97

Loop through T' = T + i * 61 for i = {0,1,2....}

Solution found at i = 443, T' = 43032 m=80.

To obtain this solution I had to factor every single T'; the last 300-
odd values were 5 digit numbers.

Michael W.

P.S. Searching through with a standard algorithm obtains the better
solution m=32 after 31 cycles and no factoring.
From: Mark Murray on 30 Jun 2010 03:34
On 30/06/2010 04:35, JSH wrote:
> Intriguingly enough my research results studying the simple system of:
>
> f_1 = a_1*k mod N thru f_m = a_m*k mod N
>
> indicate that integer factorization IS itself the key to modular
> arithmetic, so what I called surrogate factoring is in retrospect the
> way modular arithmetic operates.

Why don't you read a little?

http://en.wikipedia.org/wiki/Discrete_Logarithm
.... then go to the "Comparison with Integer Factorization" section
and look at the third bullet point.

Don't believe that? go to a search engine (any will do)
and enter "discrete logarithm factorization" (without the quotes)
to see how well understood this area is.

M
--
Mark "No Nickname" Murray
Notable nebbish, extreme generalist.
From: Tim Little on 30 Jun 2010 03:48
On 2010-06-30, JSH <jstevh(a)gmail.com> wrote:
> That result actually may eliminate the value of a large m, with k^m =
> q mod N, allowing one to easily handle it by simply cancelling out
> much of m with a simple technique equivalent to having a certain
> number of the a's equal to k^{-1} mod N.

A practical cryptographic value of m is 65537. The values for q and N
must have at least 300 digits each (RSA-1024), but numbers with 1200
digits (RSA-4096) are in practical use.


> It's a HUGE issue. So far the problem has been intractable.

It has only been intractable for the sizes of numbers given above.
RSA-512 (154 digits) has been tractable for some time.


If you can't demonstrate real-world ability to find k for arbitrary
instances where m = 65537 and q and N are 100-digit numbers, your
method is hopelessly useless, as existing methods already outperform
it by far.

But how about trying something simpler: m = 65537, and with q and N
being 10-digit numbers? In fact, here's a specific example:

k^65537 = 2328268283 mod 5123819881.

If you can solve that with a program using your method, great! You've
handled a case that existing algorithms can dispatch in a small
fraction of a millisecond. Move up to 20-digit numbers, such as

k^65537 = 3313926834980129941 mod 52453395381319443713.

This might take an older algorithm (such as my Pari script) as much as
20 milliseconds. My Pari script starts getting slow in its worst
cases at about 60 digits.


So there are plenty of tractable examples, and so far every single
example you've provided has not just been tractable, but trivial.


- Tim
 |  Next  |  Last
Pages: 1 2 3 4 5
Prev: Considering discrete logs
Next: How Can ZFC/PA do much of Math - it Can't Even Prove PAisConsistent (EASY PROOF)