I am so sorry for being bad at math.

[Aramis Wyler]

Wow, you got that symbol in there, cool. So how is '≡' different than '=' or are they not? Ah, I see hints in your answer there, like maybe the part trailing the y applies to both sides of the ≡ even though it's only written once.

[henryzz]

≡ is used over = when used in the context of congruence or equivalence relations. Strictly speaking you could say the values are not necessarily equal but are congruent whenever ≡ is used. It is silly maths notation that non-mathsy people can probably treat as equals.

[R.D. Silverman]

Originally Posted by xilman

That symbol means "is equivalent to" or "is identical to" in general. Precisely which form of equivalence depends on context.

In the context likely to be appropriate here, to say x ≡ y (mod N) means that x has the same remainder r in the range 0 ≤ r < N when divided by N as does y when divided by N.

It is HIGHLY context dependent. If you read a paper in a journal it will
NOT mean that x and y have the same remainder. Instead it will simply
mean that (x-y) is divisible by N and NOTHING MORE.

[R.D. Silverman]

Originally Posted by Aramis Wyler

huh! I've always seen the % or simply 'mod' as modulo. I'll go back and read that wiki entry again and see if that makes more sense.

EDIT: I'm not sure that follows, as the equation does use a mod.

http://www.mersennewiki.org/cgi-bin/...i?a^{p-1}\eq 1

Let P be a prime which does not divide the integer a, then a^^[I]P[/I]-1\eq 1 (mod P).

Here, it means that (a^(p-1) - 1) is divisible by p. Or, in other words
a^(p-1) - 1 is an (unknown) multiple of p.

[xilman]

Originally Posted by R.D. Silverman

It is HIGHLY context dependent. If you read a paper in a journal it will
NOT mean that x and y have the same remainder. Instead it will simply
mean that (x-y) is divisible by N and NOTHING MORE.

True. I was attempting to deduce the context from the style and location of the post.

[Aramis Wyler]

EDIT: Deleted. This comment was just a lot of me talking too much.

[Aramis Wyler]

Originally Posted by R.D. Silverman

A followup: Please see:

http://thebestpageintheuniverse.net/c.cgi?u=math

Note that I did not write it.

Wow, maybe I have taken your comments in the wrong light. I apologise for wasting your time.

[R.D. Silverman]

Originally Posted by Aramis Wyler

Wow, maybe I have taken your comments in the wrong light. I apologise for wasting your time.

You were not wasting my time. Only I can waste my time.

[xilman]

Originally Posted by R.D. Silverman

Stage 1 can not be run in parallel.

Not so..

You may not be able to parallelize the exponentiation chain but you can certainly parallelize the arithmetic primitives of addition, subtraction and multiplication within any one step in the chain. See the gpu implementation of ECM by Cyril Bouvier et al. for one way of doing it; that of Lenstra et al. for a PS2 for another; read up on Montgomery reduction within the RNS for yet another.

Paul

[R.D. Silverman]

Originally Posted by xilman

Not so..

You may not be able to parallelize the exponentiation chain but you can certainly parallelize the arithmetic primitives of addition, subtraction and multiplication within any one step in the chain. See the gpu implementation of ECM by Cyril Bouvier et al. for one way of doing it; that of Lenstra et al. for a PS2 for another; read up on Montgomery reduction within the RNS for yet another.

Paul

I have implemented parallel integer multiplication via RNS. See my paper:
Parallel Polynomial Arithmetic Over Finite Rings. (J. Parallel & Distr. Comp.) I am well aware that it can be done.

Schonhage-Strassen can also be done in parallel. But communication
costs (especially latency) among multiple GPU's makes the speed-up
that is gained succinctly sub-linear.

The best way to run P-1 in parallel is to give separate instances to each GPU.

[xilman]

Originally Posted by R.D. Silverman

I have implemented parallel integer multiplication via RNS. See my paper: Parallel Polynomial Arithmetic Over Finite Rings. (J. Parallel & Distr. Comp.) I am well aware that it can be done.

Schonhage-Strassen can also be done in parallel. But communication
costs (especially latency) among multiple GPU's makes the speed-up
that is gained succinctly sub-linear.

The best way to run P-1 in parallel is to give separate instances to each GPU.

I was aware of your paper so the "you" in my posting was very much the general reader who most likely wouldn't have read the paper in question and would be misled by your categorical "Stage 1 can not be run in parallel".

The term "best" implies optimization of a value function. While the speed-up may be sub-linear, a parallel arithmetic implementation may well be a good idea if it reduces latency to an acceptable level. Lenstra's group found this when they estimated that a GPU implementation of their PS2 ECM code would have at least an order of magnitude more throughput at the cost of several hundred times the latency. Being able to run tens of thousands of curves in parallel is attractive until you realise that it will take a year before any of them complete.