how to use big prime in meshgrid

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?

[Dyuman Joshi]

"but in matlab nnot accept the big number"

MATLAB can definitely accept big numbers, though there are limits to each data type.

p = uint64(823572345728582623)

p = uint64 823572345728582623

[X, Y] = meshgrid(0:p-1, 0:p-1);

However, the matrices you are trying to create, via meshgrid, are extremely large. Do you have enough RAM to allocate memory to define the variables?

Let's check the amount of RAM needed to create X, a uint64 matrix with size p*p -

Ram = p*p*8/uint64(1024)^3; %8 bytes per integer
fprintf('%d GBs of RAM', Ram)

17179869184 GBs of RAM

I seriously doubt your PC has this much amount of RAM. Even all the available RAM on this planet might not be sufficient.

Is it necesary for you to use such a large value of p?

If no, then lower the value of p. If yes, then it is not something anything can help you with.

[Stephen23]

One vector of 0:p-1 by itself would require:

p = 823572345728582623;
p*8 % bytes

ans = 6.5886e+18

of memory just to store it: do you happen to have more than 7 exabytes of memory installed in your computer?

And then each of X and Y would require that amount squared.... so you would need around

(p*8)^2 % bytes

ans = 4.3409e+37

That value is so large, it exceeds even the new SI prefixes. It is unlikely that your computer has more memory than the total computer storage that is estimated to currently exist on earth: current estimates seem to indicate that total computer storage is on the order of zettabytes:

https://www.statista.com/statistics/1185900/worldwide-datasphere-storage-capacity-installed-base/

... but what you are expecting to use is much larger than that.

Perhaps you need to rethink your approach.

[Mohammad]

But can do it in Java if I import Java library?

[Stephen23]

"But can do it in Java if I import Java library?"

How will using Java suddenly make your computer have more memory than all of the computer storage on Earth?

[Steven Lord]

Each of your x and y matrices would have:

p = 823572345728582623;
numberOfElements = p^2

over 6e35 elements. How large is that? If Earth had about a hundred thousand to a million times as many bacterial cells as it does now and you could store one element per bacterial cell, you could store one of those matrices.

You almost certainly will not be able to generate the list of points on this elliptic curve, certainly not through brute force.

[John D'Errico]

@Stephen23 has said it very well. Your computer, even if you have a nice big computer on your desk, does not have enough memory to store that array.

p = 823572345728582623;
% Generate all the points on the curve
% [X, Y] = meshgrid(0:p-1, 0:p-1);

And even if it did have sufficient memory, you would not have the time to do anything with it. How many elements does that array contain? I count this many:

six hundred seventy eight decillion, two hundred seventy one nonillion, four hundred eight octillion, six hundred forty eight septillion, eight hundred eighty sextillion, twenty four quintillion, two hundred thirty one quadrillion, five hundred fifty four trillion, five hundred eight billion, five hundred thirty seven million, five hundred sixty thousand, one hundred twenty nine

Suppose your computer is able to perform a trillion operations per second? That would be pretty fast. But suppose you happen to work for the NSA, or someplace with some seriously big computers. They can even beat that mark these days.

p^2/10^12
ans =
   6.7827e+23

So if you do one operation per element, so one machine cycle, per element. Let me see, if I recalll, there are something like 30 million seconds in a year.

p^2/10^12/30e6
ans =
   2.2609e+16

What is the lifetime of the universe to this date? Not quite 14 billion years I recall?

p^2/10^12/30e6/14e9
ans =
   1.6149e+06

So 1.6 MILLION lifetimes of the universe to do something with that array?

But heck, if you could use Java. Java does not do anything special, sorry. How would that make it possible to compute anything even so?

People get spoiled. They see computers on TV or in the movies do all sorts of wonderful things. But a TV show is not the real world. Computers are not infinitely large. They are not infinitely fast. They are not infinitely powerful. Computers have very finite limits.

[Mohammad]

Thanks for explanation...but I am just confused how the Elliptic curve cryptography choose the base point based on Big prime number?

[John D'Errico]

@Mohammad - that is not even a question about MATLAB. You probably need to talk with your professor.

Are you asking how to identify pairs (X,Y) such that:

mod(b*Y.^2 - ((X.^3) + (a * X.^2 + X)), p) == 0

Thus values of the integers X and Y, such that the above relation holds true, where a,b,p are given as

a = 6

b = 7

p = 823572345728582623

You cannot use brute force to solve that problem in general. If you could, then nobody would ever bother using elliptic curve crypography. It would then just get lumped in with the other trivial tools like the Ceasar cypher.

[Mohammad]

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]

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.

Answer 1

[John D'Errico]

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.

[Mohammad]

many thanks to you to give me a good idea and solution :)