how to use big prime in meshgrid

1 view (last 30 days)
Mohammad
Mohammad on 16 Mar 2023
Commented: Mohammad on 17 Mar 2023
I have this code to generate the base points:
% Define the Edwards curve parameters
a = 6;
b = 7;
p = 823572345728582623;
% Generate all the points on the curve
[X, Y] = meshgrid(0:p-1, 0:p-1);
Z = (X.^3) + (a * X.^2 + X);
idx = find(mod(b*Y.^2 - Z, p) == 0);
X = X(idx);
Y = Y(idx);
% Plot the points
scatter(X, Y);
display([X, Y]);
axis([0 p-1 0 p-1]);
title(sprintf('Points on the Montgomery curve %d*y^2=x^3+%d*x^2+x (mod %d)', a, b, p));
xlabel('X');
ylabel('Y');
but in matlab nnot accept the big number, how can I use big prime number to generate the base points in ECC?
  10 Comments
Mohammad
Mohammad on 16 Mar 2023
What I mean isif I cannot generate a base points with that big prime number because I want huge RAM resources so how can I achieve it, or how can others achieved to get base point with big prime number?
Matt J
Matt J on 16 Mar 2023
Edited: Matt J on 16 Mar 2023
how can others achieved to get base point with big prime number?
@Mohammad and as John has told you, that is not a Matlab question. You need to consult a cryptography forum, or relevant literature.

Sign in to comment.

Accepted Answer

John D'Errico
John D'Errico on 16 Mar 2023
Edited: John D'Errico on 16 Mar 2023
Pick some random integer X, less than p. You will need to use some tool capable of working with large integers, greater than the capability of a double, or even a uint64. You could use my VPI or the java.math.BigInteger tools, or SYM. Unfortunately, you will also need some other capabilities too, like a modular inverse, and a modular square root. The modular inverse is trivial, since it is effectively already in MATLAB under the guise of GCD.
a = 6;
b = 7;
p = sym('823572345728582623');
isprime(p)
ans = logical
1
So p is prime.
Now, choose a random integer less than p.
X = sym('9259113932133140')
X = 
9259113932133140
Form Z.
Z = mod((X.^3) + (a * X.^2 + X),p)
Z = 
417026731990200586
Now you want to solve for Y, such that
mod(b*Y^2,p) == Z
First, what is the modular inverse of b, mod p? You can get that from the function GCD. That is, you want to solve the problem
mod(b*u,p) == 1
For some unknown integer u. It must always exist for an odd prime p, since then 2 and p are coprime. A nice thing is, the function GCD does exactly that for you by returning coefficients that satisfy the Bezout identity. From the help for GCD, the three argument form gives you this:
[G,C,D] = gcd(A,B) also returns C and D so that G = A.*C + B.*D.
In that case, as long as b and p are relatively prime (so G==1), then the second return argument from GCD is the modular inverse of b. You would find that
[G,C,D] = gcd(b,p)
G = 
1
C = 
D = 
3
binv = mod(C,p)
binv = 
470612768987761499
So binv has the property that
mod(b*binv,p)
ans = 
1
is 1, as we needed. As such, we can now MULTIPLY by that modular inverse, because the number binv is a modular inverse.
Finally, all you need to do is compute the (modular) square root of binv*Z, so the square root in the ring of integers modulo p. In my VPIJ and VPI toolboxes, I used a method from Shanks-Tonelli to compute the sqrt.
Z = mod(binv.*Z,p)
Z = 
177228439674111887
Unfortunately, I don't have a sym code that will compute the modular square root. (I should write that and post it on the FEX one day. But my hope is that TMW will do it for me.) But in this case, you would have gotten:
Y = sym('670916485936022059');
Do X and Y have the desired property?
mod(b*Y.^2 - ((X.^3) + (a * X.^2 + X)), p)
ans = 
0
Which tells us that the pair (X,Y) are indeed a valid pair of solutions to that elliptic curve.
[X,Y]
ans = 
Perform that computation for multiple values of X. You may find that no square root exists for some values of X, probably around 50% or them. You could learn that by checking to see if Z as I computed it is a quadratic residue for p.
Anyway, all you really need is to write a modular square root code. This is your homework, not mine.
  1 Comment
Mohammad
Mohammad on 17 Mar 2023
many thanks to you to give me a good idea and solution :)

Sign in to comment.

More Answers (0)

Categories

Find more on Matrices and Arrays in Help Center and File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!