Feel free to send your feedback or ask some help here!
Hello,
I would like to know if i really understood the algo.
First of all, all the difficulty is to find the “random number” generate.
The thing with the multiple compute is because you have k-1 possibilities, so you have to choose a number that led you have the good tuple for every agents ?
The thing is we have 3 numbers to find, but only 2 equations :
[ (X1 * X + number1) %53, (X2 * X + number2) %53, (X3 * X + number3)%53 ] = [Y1,Y2,Y3]
[ (X1 * 2 * X + number1)%53, (X2 * 2 * X + number2)%53, (X3 * 2 *X + number3)%53 = [Y4,Y5,Y6]
With only Y1,Y2…,Y6, how can we know X1,X2…,X6 and the 3 numbers number1, number2 and number3 ?
Thx
1 Like
Hi Pox
The X is a bit misleading, if you try and write it down as one block you end up with too many variable and not enough equations ^^
but if you isolate it a bit it becomes more manageable:
If you consider a particular decoded letter Pi(0)
With k = 3 you have at least 3 agent values [Pi(4),Pi(2),Pi(7)]
We don’t know A[i, k-…] so lets replace them by variables A, B,C
we end up with:
A * X^2 + B * X + Pi(0) = resOfPi(X)
Still to many variables
But X is actually known
004: A * 4^2 + B * 4 + Pi(0) = resOfPi(4)
002: A * 2^2 + B * 2 + Pi(0) = resOfPi(2)
007: A * 7^2 + B * 7 + Pi(0) = resOfPi(7)
As you have the result for each line you are left with the unknowns:
A -> irrelevant but common to all agents
B -> irrelevant but common to all agents
Pi(0) -> the decoded letter
And this where I’m stuck trying to find a generic why to resolve up to 9 variable linear equations 
Hope this helps
1 Like
@Pox I think the answer by @anarkia1985 should put you on the right track. Also, to make it clear, you always have enough equations (you can actually even have more than needed), as stated in the constraints section:
It is guaranteed that N≥k the threshold that was used to share the secret.
1 Like
Hi, my code already solves some cases, but somehow, some cases fail… I found out it is due to the modulo 53 on the inputs : If I calculate an agent piece using a given polygone, I find a number greater than 53 (most of the time), if I use those numbers to uncover the original letter, I do find the write one. However using those numbers modulo 53 (which is the given input), I don’t…
Do you have any leads for me ? @Niako
@jcho I answered (asking for more information about your solution) in PM to avoid spoiling too much here.
Java default code is wrong.
There is “int i” in the for-loop as well as for the “nextInt” instruction…
2 Likes
@TheFalk Indeed, that’s because I had used i as an input variable name while it’s also the default variable name used by the stub when generating loops. I fixed it, thanks.
1 Like
Hi Anarkia1985,
I performed the linear system resolution using Gauss-Jordan algorithme, but I still get wrong answer.
is there any tip that I can follow?
thanks
It seems that I solved it without a GauĂź algorithm.
2 Likes
Gaussian elimination is not the optimal approach, but it works as well.
2 Likes