Posts by arina

arina · Maths Is Fun - Suggestions and Comments

Hi,

The logout button on the left side-panel doesn't work. I stay logged in until i click 'Logout' on the top-of-the-page menu. I'm using Firefox.

Thought I'd let u know.

arina · Help Me !

Hi again Bobby,

I've spent the week investigating how Chinese Remainder Theorem is used in RSA cryptography. Turns out, you were right. These problems really do fight back till the end.

From what I've seen, CRT usually reduces variable size by half (roughly speaking). So if the original value is up to 1024, CRT can be used to reduce the calculation size to 512 but the calculations have to be performed at least twice. So, a 200 bit binary number can be reduced to 16 bit binary remainders but the moduli will be around 100 bit binary numbers.

So now I'm looking at Zech's Logarithms in trying to solve the issue. Would you happen to know any resources that give simplified explanation and example on how to implement this Zech Log (aka Jacobi Logarithm)?

Thanx.

arina · Help Me !

Hi bobby,

Wow, that's a very clear explanation. Looks like this could work. I'm starting to see the light at the end of the tunnel.

So how do I decide how many GFs I need to be able to solve the problem? In general, are four GFs enough to determine the original number with high accuracy? Even if the number is

?

And I can't use the same four GFs for all the points of my polynomial? Is that because of the extreme difference in size between the smallest y-value(414) and the largest(1677930)?

My aim is to reduce the coordinate value to a 16 bit number or numbers, meaning the finite field values have to fall between 1 and 65535. In this case I can't choose the moduli such that the answer is smallest, at least for the larger numbers. So, say I'm reducing 1677930 to finite field. I choose four GFs: GF(65521), GF(65519), GF(65497) and GF(65479).

So, if I save these numbers, I can get back the original 1677930 using Chinese Remainder Theorem? How's that work?

Thanx.

arina · Help Me !

Alright, thanx Bobby. So, this confirms that the slight inaccuracy was caused by lack of decimal points in my coefficients. Unfortunately, my program can't handle fractions either. But that's ok, I'll work on a way to overcome this limitation.

Meanwhile, back to my original question. I have a polynomial:

I find four points lying on the polynomial: (0,2514), (1,414), (2,3142) and (3,1677930)

If I were to reduce the points to a finite field, say GF(251) or GF(241), etc. and store the points in a database, how could I recover the original polynomial by performing Gaussian Elimination on the finite field points?

(0,2514), (1,414), (2,3142) and (3,1677930) == (0, 4 + 10*251), (1, 163 + 1*251), (2, 130 + 12*251), and (3, 246 + 6684*251)

Finite field points in database: (0,4), (1,163), (2,130) and (3,246).

Is there a way that I can get rid of the numbers: 10, 1, 12 and 6684 yet still be able to recover the original polynomial? Frankly, saving these values would cause a security threat to the scheme and make it vulnerable to brute force attacks.

arina · Help Me !

Ok. So what is the best polynomial fit for these points? I thought maybe the polynomial was slightly off because my program can't allow the coefficients to have decimal points.

And why are these points better than using the points I gave for the original polynomial? (0,4), (1,163), (2,1888) and (3,6685)
Is the polynomial one of those that cannot be uniquely determined?

Thanx.

arina · Help Me !

Hi Ricky,

Thanx for pointing that out. I'd forgotten to add another point since it was a 3rd degree polynomial. Sure, we can use the points you listed and try to reconstruct the polynomial that they define.
(0, 4 + 10*251), (1, 163 + 251), (2, 1888 + 5*251), and (3, 6685 * 251) == (0,2514), (1,414), (2,3143) and (3,1677935) Right?
Using Gaussian Elimination, the polynomial that passes thru them is:

However, I found this polynomial gives slightly different values for x = 2 and x=3 which are 3142 and 1677930 respectively. I wonder why that's happening.

One requirement that my program must fulfill is that the x-y coordinates as well as the polynomial coefficients must be Whole numbers. No floating points possible.

Hi Bobby,

CRT? Hmmm, I've heard other cryptography researchers mention it. Does that mean we'll need to have four coordinate values for each point to successfully rebuild the polynomial? I'm gonna go study up on how this CRT works.

Regarding my references, the engineering papers that I read regarding the security system I'm trying to build mentioned the finite field almost like an after-thought. I've created the rest of the security system and it works fine for small numbers like this cubic equation (since my real finite field is 0 to 65001). I have to write a program where the polynomial coefficients and x-coordinates are provided by the user during the encoding/hiding part. It must be between an 8th degree to 14th degree polynomial. The finite field isn't fixed either, it just has to be from 0 to around 65000 or so. It can be prime field or binary field since I've seen papers that use both.

So, there's no fixed polynomial equation and I must be able to solve any and all polynomial equations of 8th degree. During the decoding part, the user provides the right x-coordinates, the database provides the matching y-coordinates and my program must reconstruct the original polynomial. The program has to give back the exact polynomial coefficients to successfully complete the decoding process.

I'm listing the maths literature that I've been reading in trying to find the answer.

Polynomial Codes Over Certain Finite Fields at kom.aau.dk/~heb/kurser/NOTER/KOFA01.PDF
Construction of Galois Fields of Characteristic Two and Irreducible Polynomials at http://www.jstor.org/stable/2003204
Calculations in Galois Fields at http://www.drdobbs.com/cpp/184401858
Hardness of Reconstructing Multivariate Polynomials over Finite Fields at http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=04389506
Solving Large Sparse Linear Systems Over Finite Fields at http://www.farcaster.com/papers/crypto-solve/solve.html

If you can't access some of the sites, please let me know where I can email them to you.

Bobby and Ricky, thanx again for taking the time in trying to help me. Looking forward to some advice/solution.

arina · Help Me !

Hello all,

I was wondering if anyone could help me with the math part of my university project. Say I have a polynomial equation like so:

Now if I were to find three points on this polynomial, they would be:

and.

The problem is that I need the points to be in a positive finite field with an x and y range of 0 up to 251. So I make the points part of this finite field GF(251) and they become:

and

The problem arises when I have to get back the original polynomial by performing Gaussian Elimination using these finite field points. One way could be to save the values 0, 7 and 26 to be multiplied by 251 and added to the new y-coordinate values so that I get back the original y-coordinates. That way I can reconstruct the polynomial. But storing these values is unpractical and a security threat, so I can't do that.

My question: How can I re-create the above polynomial using the finite field coordinate locations?

Trivia:
I'm working on an electronic security system that contains cryptography as well as error-correction. I'm currently designing the system in C (which, by the way can only store integer values up to 0xFFFFFFFF) but later on the compute intensive parts must be designed as hardware blocks in Verilog. My actual polynomial is 8th degree with coefficient values that can range from 0 to 0xFFFF. My x-y finite universe is from 0 to 65025. Currently I can't even store the original values in C variables since if

. Storing any kind of extra values (like: 0, 7 and 26) can cause security risk since an attacker could more easily compromise the system. And I've seen journal papers about such security systems that use finite fields and can still reconstruct the polynomial. Searching maths journal papers, I found the explanations full of jargon and I couldn't understand. Any ideas or suggestions (or even better: the solution) would be much appreciated.

Thank you.

arina · Help Me !

Hi John,

I'm happy to say that I've finally managed to solve the maths problem completely.

I used triple 'for' loops containing 'if' statements to display the result. Now, I think I'll create a sub-routine for it to average the results and give me one final answer. But it looks like smooth sailing from here on.

I'd like to once again thank you from the bottom of my heart. If it wasn't for your help, I might have spent another two or three long months to get this far, or maybe i would've just given up and handed in incomplete work.

You must have spent a few hours at the very least working on this maths problem for me, a complete stranger. And I wanted you to know that I truly appreciate your kindness.

Thanks ever so much.

arina · Help Me !

I've been 'cracking my head' trying to figure out a way to print out the matching coordinates. It seems so strange that the graph is showing the coordinates clear as day but I can't figure out the code to print the coordinates as program output.

I've been going through all possible command searches in the 'matlab help'. I've tried matlab commands like 'intersect', 'diff', etc. I'm trying the loop method you mentioned now.

I've heard that Matlab is rarely used in the industry since the price of 'non-academic purpose' license is sky-high. Still its great for Signal Processing and some of my professors swear by it. Here's a short version of my matlab code so far:

x = -60:0;		   	     % Selecting range of x and y.
y = 0:60;
x1 = x.*x;			       % Square each element in the x matrix.
y1 = y.*y;

for a=1:length(x)
for b=1:length(y)
z1(a,b)=x1(a)+y1(b);	     % Create a MATRIX that contains all possible   
end				  	    % combinations of x (squared) + y (squared). 
end 				         % [MATRIX dimensions: 61 x 61]
mid = (-127-x);         	 % Create a matrix of (-127 - x) for all x values.
x2 = mid.*mid;          	 % Square each element.
ymid = (100-y);			  % Create a matrix of (100 - y) for all y values.
y2 = ymid.*ymid;

for a=1:length(x)
for b=1:length(y)			% Second MATRIX for all possible results for the
z2(a,b)=x2(a)+y2(b);		 % second part of the equation.
end				 	     % [MATRIX dimensions: 61 x 61]
end 

z3=sqrt(z1);				 % Find square-root of the first
z4=sqrt(z2);				 % and second MATRIX.
delta = z3 - z4;

% Locate all results within this range:	      xo = row number
[xo,ya,v] = find(-32 < delta & delta < -28)	% ya = column number					
% The row values / x-coordinates are changed from 0 -> 60 to -60 -> 0.
xa=xo-60;

% Repeat same procedure for 2nd and 3rd equations........
% Result: 3 sets of coordinates: xa, ya, xb, yb and xc, yc
% Plot the graphs:
plot(xc,yc,'d',xa,ya,'.', xb,yb,'o')

I've chosen to plot dots instead of lines too. The coordinates given are whole numbers since the accuracy is good enough for me.

Now, back to 'head-cracking' for me.

arina · Help Me !

Pretty impressive list! So, is Euphoria considered 'programming'?

I used your program as a guide to write Matlab code and succedded in getting the graphs/plots for the three equations. Only things is now I can't extract the x and y values where the graphs intersect.

I modified the Basic code you gave like this:

And I added the conditions for JQ2 and JQ3 in the printing sections of the program. Fortunately, that gave a narrowed set of possible coordinates.

What command could I add to your Just Basic code so that it lists out the possible coordinates as output? And what do you think is the equivalent C command? I can transalate C commands into Matlab easier.

arina · Help Me !

Oh, wow. That's a neat little program. Thank you so much for posting it. I downloaded just Basic and now I'm trying to understand the code.

I used it to create the graph for my first equation and I can see that it gives a set of possible results that include the correct answer. I guess if I could somehow plug in the other two equations I could narrow it down to one correct answer.

The past couple of days, I decided to use Matlab software to find the correct values through a trial & error method. Since matlab is quite reliable in computing vast amount of data quickly, I created a matrix of all possible combinations of x and y values. After a lot of troubleshooting, I've managed to narrow down the first equation to 118 possible results. I'll have to find a way to match results for all three equations to find the final correct x and y coordinate.

By the way, I'm curious as to why you've chosen Basic. Is it a better programming language for mathematical problems? I've never written a program for mathematical problem that has graphical solution. Do you think C can produce this kind of graph too?

But no matter what, it looks like my maths problem won't be a problem for long. :-)

arina · Help Me !

Wow, I think the dot method is pretty good. Which software do you use for this, John? Initially I tried using Matlab and Polymath to try and solve this problem. But they can't really solve implicit equations. So I thought if I could just figure it out manually, then maybe I could write a program for it. But your graphical method seems perfect for this.

Hmmm, I haven't tried using hyperbola function in Matlab. I'll go and try it out now.

If you figure it out, please let me know. I'll be greatly indebted to you. Thanx.

arina · Help Me !

Wow, that was fast. Thank you for your help, John. I really appreciate it.

I've spent 4-5 hours trying to work my equations like that but whenever I've replaced the real values of x and y into the equations i get absurd values. In theory the final result should be equal in both sides like

But for my own equations i got strange values in every attempt. Some results for your entertianment:

Finally I used the equation given under the subtopic An Equation for a Hyperbola.
I drew the points on a piece of paper with the middle being

. was at and f2 at so that .

I selected a random coordinate

as the that had to be found. Difference in distance: . (Here the distance and coordinates are in milimeters)

Working the values into equation (8) of the webpage you pointed out, I got this result:

I am absolutely baffled by what I'm doing wrong.

I know your time is very precious. I am deeply humbled by the help you have given so far. But could you help me out a little and maybe point my mistake here? I'll be grateful for any pointers. Thanx.

arina · Help Me !

Oops, I've made a terrible, terrible mistake. I somehow left out the negative signs in the left side of the equation. Here's the correct ones:

I'm really, terribly sorry for the error.

Actually, the answer is integral whole numbers. For the above set the correct answer is

You might have noticed that these are the standard distance equations used for Cartesian coordinate geometry. Actually my original distance values were different. I thought maybe I had the wrong distance values. So I chose these coordinates myself by measuring the distance. What I really need is a method to solve these equations repeatedly for different distance values. I gotta code a program that does it automatically. Don't ask me why they keep telling us to write new programs when there are so many maths software available already. But my deadline is fast approaching and I'm out of ideas.

Could anyone please help me out, give me some guidance? Please?

arina · Help Me !

Hallo,

I'd like to request a little help with this perplexing problem. I have three equations with two unknowns but so far I haven't been able to solve for exact values of x and y....

I haven't figured it out using log or any numerical method so far.

A solution or even some advice would be much appreciated.

Thanx.

Math Is Fun Forum

#1 Maths Is Fun - Suggestions and Comments » Logout issue » 2010-03-11 19:34:59

#2 Re: Help Me ! » Polynomial Reconstruction in Finite Field » 2010-03-11 19:29:49

#3 Re: Help Me ! » Polynomial Reconstruction in Finite Field » 2010-02-24 15:17:58

#4 Re: Help Me ! » Polynomial Reconstruction in Finite Field » 2010-02-23 14:35:54

#5 Re: Help Me ! » Polynomial Reconstruction in Finite Field » 2010-02-22 14:32:35

#6 Re: Help Me ! » Polynomial Reconstruction in Finite Field » 2010-02-21 16:44:01

#7 Help Me ! » Polynomial Reconstruction in Finite Field » 2010-02-18 22:37:37

#8 Re: Help Me ! » Non-linear Simultaneous Equations problem. » 2007-09-23 16:36:46

#9 Re: Help Me ! » Non-linear Simultaneous Equations problem. » 2007-09-17 16:15:11

#10 Re: Help Me ! » Non-linear Simultaneous Equations problem. » 2007-09-16 20:51:49

#11 Re: Help Me ! » Non-linear Simultaneous Equations problem. » 2007-09-13 20:15:49

#12 Re: Help Me ! » Non-linear Simultaneous Equations problem. » 2007-09-11 14:27:16

#13 Re: Help Me ! » Non-linear Simultaneous Equations problem. » 2007-09-10 16:06:03

#14 Re: Help Me ! » Non-linear Simultaneous Equations problem. » 2007-09-09 13:52:10

#15 Help Me ! » Non-linear Simultaneous Equations problem. » 2007-09-06 12:58:16

Board footer