Re: Breaking Large Composite Numbers...???

On Dec 16, 2:14 pm, Phil Carmody <thefatphil_demun...@xxxxxxxxxxx>
wrote:
Pubkeybreaker <pubkeybrea...@xxxxxxx> writes:
On Dec 16, 11:02 am, Christian Siebert <iB...@xxxxxx> wrote:

<snip>

If you'd done (3), then you would notice that these
sparse matrices don't remain sparse as you process them.

My mistake, thanks for this tip - you're right of course.

Actually,  you are both very wrong.  Iterative methods such
as Block Lanczos and Block Wiedemann maintain the sparseness
of the original matrix.

Gaussian elimination, OTOH gets rapid fill-in.

I don't think you'll find me ever denying that. That's why GE's
not used - density is the enemy. You quickly lose the sparseness
and fall back onto O(n^3) with a huge n. However, it's at this
the point where Christian is comparing behaviour to that of the
top500 supercomputers. On dense matrix operations. However, his
'n' was wildly out, that's my point. If you don't like my
response to his 'equals' statement, which you seem not to, then
please compose your own.

O(n^3) is overly pessimistic. Strassen matrix mulitplication is
actually practical at rather small sizes today and is O(n^2.8).
http://matrixprogramming.googlegroups.com/web/strassen.zip

I guess that if you are talking about titanic matrix sizes, then this
algorithm may become worthwhile:
http://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm

I think that absurdly large prime factors make sense in some
contexts. For instance, if we are trying to protect a bank account
that contains a total of $10,000 then 512 bit prime sizes are
certainly more than plenty large enough. The search to solve the
puzzle will be worth far more than the prize received, and so it makes
no sense to tackle that problem.

But suppose that we are protecting critical nuclear weapon design
information. What size would be sufficient to make you feel fully
comfortable, knowing that for a few thousand dollars you can get a 1
TFlop machine that runs off of a stack of graphics cards? What if
terrorists bought 1000 of those machines in an effort to steal that
data? If someone told me that they were using 10,000 bit primes to
protect that data I would not feel that it was a waste of compute
power.
[snip]
.

Quantcast