mod p calculation help

[kurtulmehtap]

Dear All,
I need to calculate X = (p-1/ 2q ) mod p
where p and q are primes.
Is there a better way than doing modular division?

[Ken_g6]

Edit: No, I don't think I know of a better way, except that you can simplify (P-1) mod P.

Is this homework?

[kurtulmehtap]

It's not homework,
I need to write a program that repeatedly calculates
X = (p-1/ 2q ) mod p

where p and q are primes and list the results starting from p=3 to q.

Instead of calling the Modular division subroutine every time I have a new prime p,
I would prefer to have a faster way.
In this case better means faster and simpler.
Thanks

Originally Posted by Ken_g6

Define "better". Simpler? Probably not. Faster? Maybe.

Is this homework?

[R.D. Silverman]

Originally Posted by kurtulmehtap

It's not homework,
I need to write a program that repeatedly calculates
X = (p-1/ 2q ) mod p

where p and q are primes and list the results starting from p=3 to q.

If q is fixed and p varies, then I know no faster way.

There is a faster way if p is fixed and q varies.

Instead of calling the Modular division subroutine every time I have a new prime p,
I would prefer to have a faster way.
In this case better means faster and simpler.

What could be simpler than the Euclidean algorithm?

If p is LARGE, I would recommend using a binary Extended Euclidean
Algorithm, rather than a classical one. If p is VERY LARGE, I would use
an FFT approach.

How big are p and q?