Prev: Updating the Historic OTP.
Next: CFP DATA MINING 2010: new date - until 29 March 2010
From: David Eather on 25 Mar 2010 18:25
On 26/03/2010 1:33 AM, adacrypt wrote:
> On Mar 24, 12:34 pm, Tom St Denis<t...(a)iahu.ca> wrote:
>> On Mar 24, 7:57 am, adacrypt<austin.oby...(a)hotmail.com> wrote:
>>
>>
>>
>>
>>
>>> On Mar 23, 7:53 pm, Martin Lauridsen<martinlaurid...(a)gmail.com>
>>> wrote:
>>
>>>> On 23 Mar., 18:27, Pubkeybreaker<pubkeybrea...(a)aol.com> wrote:
>>
>>>>> What is "this"? Are you asking why B^2- 4AC is 0 or 1 mod 4?
>>>>> Or are you asking why it must equal k*N (not just N) for some
>>>>> selected multiplier k?
>>
>>>>> If the former, observe that all squares are either 0 or 1 mod 4 [do
>>>>> you see why?]
>>>>> and that 4AC is 0 mod 4.
>>
>>>>> We are trying to find polynomials f(x) such that g^2(x) = f(x) = a
>>>>> mod N
>>>>> and also that p divides f(x), f(x+p), f(x+2p) .... for certain
>>>>> primes p (primes in the factor base)
>>>>> Now solve f(x) = 0 mod p using the quadratic formula mod p and use
>>>>> the fact that p is
>>>>> a quad. residue of kN. If the discriminant is not a square mod N,
>>>>> then the polynomial will not
>>>>> generate squares mod N.
>>
>>>> Hi Pubkeybreaker.
>>
>>>> I see that any square must be 0 or 1 (mod 4), since we have four
>>>> cases:
>>
>>>> a = 0 (mod 4) => a^2 = 0 (mod 4)
>>>> a = 1 (mod 4) => a^2 = 1 (mod 4)
>>>> a = 2 (mod 4) => a^2 = 4 = 1 (mod 4)
>>>> a = 3 (mod 4) => a^2 = 9 = 1 (mod 4)
>>
>>>> Yes, I understand that we must find some polynomial, lets call it
>>>> Q(x), which generates squares (mod N).
>>>> I have already implemented this, for the single polynomial case. Here
>>>> I use Q(x) = (x + m)^2 - N, where m = floor(sqrt(N)).
>>
>>>> We want Q(x) to produce a lot of values, that are smooth with regard
>>>> to the factor base, for a somewhat small interval [-M, M].
>>>> I am in doubt how to choose the coeffecients A, B and C in Q(x) = Ax^2
>>>> + Bx + C, to obtain this.- Hide quoted text -
>>
>>>> - Show quoted text -
>>
>>> Hi Martin,
>>> This is exactly the kind of discussion that I am promoting in my
>>> poster below. Your discussion prompts me a follows. I will dive in
>>> quickly with the outline of what might be another very elegant
>>> adaptation of the Vigenere cipher. This is only a suggestion but it
>>> is worth researching. I am tempted to keep it to myself but that
>>> would be plagiarism - some thing I despise !
>>
>> <snip>
>>
>> I love how despite the fact he has no idea what he's talking about or
>> what the QS is, he decides to inject himself in the conversation.
>> Awesome.
>>
>> Tom- Hide quoted text -
>>
>> - Show quoted text -
>
> Ok - I got it wrong - I was out of my depth and indeed barking up the
> wrong tree without realising it - apologies to all concerned.
>
> This of course means as applied to cryptography.
>
> I believe I have proved the theorem in passing although nobody wants
> to know that in the face of the bigger issue of factorizing giant
> numbers.
>
> I honestly suspect that will not come in time to be of any great value
> in cryptography but there I go again jumoing the gun.
>
> Regards - Austin O' Byrne

Um, *NOT* being able to factor giant composite numbers is what allows
public key cryptography to work. Factoring is of interest because it
gives confidence in the public key methods and points to the size of
numbers that are needed for safety.
From: adacrypt on 26 Mar 2010 07:31
On Mar 25, 10:25 pm, David Eather <eat...(a)tpg.com.au> wrote:
> On 26/03/2010 1:33 AM, adacrypt wrote:
>
>
>
>
>
> > On Mar 24, 12:34 pm, Tom St Denis<t...(a)iahu.ca>  wrote:
> >> On Mar 24, 7:57 am, adacrypt<austin.oby...(a)hotmail.com>  wrote:
>
> >>> On Mar 23, 7:53 pm, Martin Lauridsen<martinlaurid...(a)gmail.com>
> >>> wrote:
>
> >>>> On 23 Mar., 18:27, Pubkeybreaker<pubkeybrea...(a)aol.com>  wrote:
>
> >>>>> What is "this"?  Are you asking why B^2- 4AC is 0 or 1 mod 4?
> >>>>> Or are you asking why it must equal k*N  (not just N) for some
> >>>>> selected multiplier  k?
>
> >>>>> If the former, observe that all squares are either 0 or 1 mod 4  [do
> >>>>> you see why?]
> >>>>> and that 4AC is 0 mod 4.
>
> >>>>> We are trying to find polynomials  f(x)  such that g^2(x) =  f(x)  = a
> >>>>> mod N
> >>>>> and also that  p divides f(x),  f(x+p),  f(x+2p) ....   for certain
> >>>>> primes p   (primes in the factor base)
> >>>>> Now solve  f(x) = 0 mod p   using the quadratic formula mod p and use
> >>>>> the fact that p is
> >>>>> a quad. residue of kN.  If the discriminant is not a square mod N,
> >>>>> then the polynomial will not
> >>>>> generate squares mod N.
>
> >>>> Hi Pubkeybreaker.
>
> >>>> I see that any square must be 0 or 1 (mod 4), since we have four
> >>>> cases:
>
> >>>> a = 0 (mod 4) =>  a^2 = 0 (mod 4)
> >>>> a = 1 (mod 4) =>  a^2 = 1 (mod 4)
> >>>> a = 2 (mod 4) =>  a^2 = 4 = 1 (mod 4)
> >>>> a = 3 (mod 4) =>  a^2 = 9 = 1 (mod 4)
>
> >>>> Yes, I understand that we must find some polynomial, lets call it
> >>>> Q(x), which generates squares (mod N).
> >>>> I have already implemented this, for the single polynomial case. Here
> >>>> I use Q(x) = (x + m)^2 - N,   where m = floor(sqrt(N)).
>
> >>>> We want Q(x) to produce a lot of values, that are smooth with regard
> >>>> to the factor base, for a somewhat small interval [-M, M].
> >>>> I am in doubt how to choose the coeffecients A, B and C in Q(x) = Ax^2
> >>>> + Bx + C, to obtain this.- Hide quoted text -
>
> >>>> - Show quoted text -
>
> >>> Hi Martin,
> >>> This is exactly the kind of discussion that I am promoting in my
> >>> poster below.  Your discussion prompts me a follows.  I will dive in
> >>> quickly with the outline of what might be another very elegant
> >>> adaptation of the Vigenere cipher.  This is only a suggestion but it
> >>> is worth researching.  I am tempted to keep it to myself but that
> >>> would be plagiarism - some thing I despise !
>
> >> <snip>
>
> >> I love how despite the fact he has no idea what he's talking about or
> >> what the QS is, he decides to inject himself in the conversation.
> >> Awesome.
>
> >> Tom- Hide quoted text -
>
> >> - Show quoted text -
>
> > Ok - I got it wrong - I was out of my depth and indeed barking up the
> > wrong tree without realising it - apologies to all concerned.
>
> > This of course means as applied to cryptography.
>
> > I believe I have proved the theorem in passing although nobody wants
> > to know that in the face of the bigger issue of factorizing giant
> > numbers.
>
> > I honestly suspect that will not come in time to be of any great value
> > in cryptography but there I go again jumoing the gun.
>
> > Regards - Austin O' Byrne
>
> Um, *NOT* being able to factor giant composite numbers is what allows
> public key cryptography to work. Factoring is of interest because it
> gives confidence in the public key methods and points to the size of
> numbers that are needed for safety.- Hide quoted text -
>
> - Show quoted text -

Just out of curiosity.

I have done some considerable work in the past factoring large numbers
by conventional methods and for some time I wrongly believed that the
crunch came when the computer could not store the very large parent
number being tested by the string of candidates ie. the largest +ve
integer that can be stored in 32 bit arithmetic is 2147483647. I next
assumed that because of this the computation would have to be done
externally by hand - hence the time taken ? Current research is into
methods that will get around this ? How rigth or wrong is this
hypothesis ?

Something to consider in my view is graphical arithmetic using GPS to
approximate very close with some error analysis ?
From: Maaartin on 26 Mar 2010 07:56
On Mar 26, 12:31 pm, adacrypt <austin.oby...(a)hotmail.com> wrote:
> I have done some considerable work in the past factoring large numbers
> by conventional methods and for some time I wrongly believed that the
> crunch came when the computer could not store the very large parent
> number being tested by the string of candidates ie. the largest +ve
> integer that can be stored in 32 bit arithmetic is 2147483647.  I next
> assumed that because of this the computation would have to be done
> externally by hand - hence the time taken ?  Current research is into
> methods that will get around this ?  How rigth or wrong is this
> hypothesis ?
>
> Something to consider in my view is graphical arithmetic using GPS to
> approximate very close with some error analysis ?

OOO M M GGGG
O O MM MM G G
O O M MM M G
O O M M G GG
OOO M M GGGG

You may need a fixed size font to decrypt the message. :D
From: Tom St Denis on 26 Mar 2010 08:49
On Mar 26, 7:56 am, Maaartin <grajc...(a)seznam.cz> wrote:
>  OOO    M    M   GGGG
> O   O   MM  MM  G    G
> O   O   M MM M  G
> O   O   M    M  G   GG
>  OOO    M    M   GGGG
>
> You may need a fixed size font to decrypt the message. :D

See it isn't that there is a small intersection of "reality" and "what
Adacrypt" knows, it's that it defines a null space.

What I love about him so much is that he so confidently announces how
nothing he knows is relevant to any conversation at hand. He's like
the little 5 yr old kid tugging at an adults shirt to try and add to a
conversation between adults. You know the kid has nothing useful to
say but you still like hearing them spout off their insanity just the
same.

Tom
From: Noob on 26 Mar 2010 09:08
adacrypt wrote:

> Just out of curiosity.
>
> I have done some considerable work in the past factoring large numbers
> by conventional methods and for some time I wrongly believed that the
> crunch came when the computer could not store the very large parent
> number being tested by the string of candidates i.e. the largest +ve
> integer that can be stored in 32 bit arithmetic is 2147483647. I next
> assumed that because of this the computation would have to be done
> externally by hand - hence the time taken ? Current research is into
> methods that will get around this ? How right or wrong is this
> hypothesis ?
>
> Something to consider in my view is graphical arithmetic using GPS to
> approximate very close with some error analysis ?

(You and JSH should meet. You'd be quite the dynamic duo.)

http://en.wikipedia.org/wiki/Bc_programming_language
http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic

I've spent years working on the factoring problem, and I've
shattered this 32-bit limit you mention.

#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>

void trialdiv(uint64_t n)
{
uint64_t i;
for (i = 3; i*i <= n; i += 2)
{
while (n % i == 0)
{
n = n / i;
printf("%llu x ", i);
}
}
printf("%llu\n", n);
}

int main(int argc, char **argv)
{
uint64_t n = strtoull(argv[1], NULL, 0);
trialdiv(n);
return 0;
}

Ha! Take that, Pubkeybreaker!
Your 64-bit keys are no match for my wizardry.

Regards.
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5
Prev: Updating the Historic OTP.
Next: CFP DATA MINING 2010: new date - until 29 March 2010