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

On Dec 15, 10:41 am, Christian Siebert <ib...@xxxxxx> wrote:
Pubkeybreaker wrote:
And recent factorizations have shown this.  We could
(practically, not just theoretically) throw 100's of
thousands (or more) computers as the sieving phase
of NFS.

Nevertheless, sieving is just a form of simple linear search. How about
finding relations in a more elegant way or even constructing/computing
them ...?

Please explain what you mean by "more elegant". Sieving is an
extremely
efficient procedure on today's computers.

What do you mean by "constructing them"? And how does "constructing
them"
differ from "computing them"? By any reasonable definition of
"computing",
NFS does compute congruences.

Without definition, you comments are meaningless.


Memory would be a problem.  As would the OS.
factoring a 1024-bit RSA would require computers
with a 64-bit address space (and while they are becoming
more common, it will be a while before they are prevalent;
most are still 32 bits)  and about 32 Gbytes of memory
each.

64-bit is getting quite common - even the discounters are now selling
such desktop machines, while 32-bit processors seem to be sold less and
less (e.g. in mobile computers). And memory is also quite cheap these days!

Yep. It is getting cheap. But the memory requirements for 1024-bit
RSA are
still well beyond what is normally affordable. Please suggest when
you think
that the standard PC sold at Circuit City or Best Buy will be a 64-bit
PC with
32 Gbytes of memory. Think about "market demand" for such machines.

And the LA for a 1024-bit number will require a machine
with somewhere between 1 and 10 Tbytes of memory..
(my best estimate is about 3 Tbytes)

Looking atwww.top500.orgit seems that there are already hundreds of
supercomputers that have more than your 10 TiB of memory.

These are message passing MIMD computers. The LA for NFS does not
scale
on such architectures. The processor-to-processor interconnects are
TOO
SLOW.



Since there exists already lot's (sic) of machines that fit your technological
needs,

FALSE. We do not have lots of machines with 32Gbytes of memory. And
please
identify even a single computer with 10Terabytes that is not a cluster
of machines.

Noone has even been able to get a 25% utilization out of 100 machines
running in
parallel. Utilization has been scaling aproximately as the square
root of the
number of processors on *tightly coupled* machines. The
supercomputers of which
you speak are not *tightly coupled*.



I don't think that this is the real burden.


Allow me to ask: how much actual experience do you have? Have you
ever factored a number of even 512 bits? Have you implemented any
sparse linear algebra code in parallel?

If you answer no, then I would ask what qualifies you to have an
opinion on the subject???


Unless there is an algorithm breakthrough.

But especially this was the most effective contributor in the history of
integer factorization (not the comparably minor increase of computing
power over the years)!

WRONG, WRONG WRONG. Contributions towards record factorizations have
come
about equally from both. If you thin otherwise, I suggest you try to
implement
NFS on a computer from (say) 25 to 30 years ago. Try it on a CDC
6600, a Cyber-205,
a Cray-1, or an IBM 370 class machine. Even if you could collect
10000 such machines,
they did not have enough memory to run the algorithm.

Even today, NFS suffers mostly from space limitations and memory/
communication
latency problems.

Agreed. Can we take the fact that RSA labs stopped its famous challenge
as an indication that such an algorithmic breakthrough happened (or is
close to happen soon)???

No. You can blame the accountants. RSA was required to carry any
potential
payouts as a liability on its balance sheets. They also acquired the
attitude that
it was no longer necessary to promote factoring research.

.