painful maths that will hurt your brain...

So , im working with logarithms and modulus all in one brain hurtingly go. I currently have 7 = log x (274625) % 17 how would I derive the base (x) from that equation. I am utterly butterly lost and cant think of anything apart from rhyming words and sleep.

Is it solve for X?

First thing I would do would be to break it into two pieces. But I’m not sure what the two pieces would be.

Is it

(log x (274625) % 17

–or–

log x ((274625) % 17 )

??

I’ve never solved an algebraic equation with a modulus before. It seems to me that the modulus implies that X could be a series of numbers rather than a single number.

For example, if the question were solve for X:

7 = Y % 17, the answer would be

Y = (n * 17) + 7

Some hotshot will have an answer for you, I bet, before too long.

well i aint no fancy pants skolar with dem book smarts…

so I turn to wolframalpha for these sorts of problems :slight_smile:

so it has given me:

x = 0.285842 or 5.9836 as possible values for x

source: http://www.wolframalpha.com/input/?i=logx(274625)+mod+17%3D7

it is 7 = (log x (28274625))%17 If I give you the clue that 282724625 is 65^3 would that help , so for calculating the inverse of the modulus. Some steps would be very useful , thanks.

So here are my thoughts for what they are worth, bearing in mind I have also never done any algebra with modulos. But I agree with @philfrei about that being the way to solve it and the whole infinite answers of x thing. @moogie I suspect the reason Wolfram told you otherwise is that it either interpreted “log x(28274625)” as “log of (x times 28274625)” rather than “log base x of 28274625” or it misinterpreted the modulo symbol or both.

So:

7 = logx(28274625) % 17

(n * 17) + 7 = logx(28274625) Where n = 0, 1, 2, 3… (not -ve since log(a) > 0) using @philfrei’s equation.

Now it gets a bit hairy.
Take the change of base log formula

logb(a) = logd(a) / logd(b)

logd(b) = logd(a) / logb(a) Making the original base, b, the subject.

ln(b) = ln(a) / logb(a) Just for jollies lets make d = e -> logd(a) = ln(a)

b = e^( ln(a) / logb(a) )

Now lets sub the original equation into that. b = x, a = 28274625, logb(a) = (n * 17) + 7

x = e^( ln(28274625) / ( (n * 17) + 7 ) )

Giving some example answers (to 4dp): (n = 0, x = 11.6007), (n = 1, x = 2.0440), (n = 2, x = 1.5196) etc. and you can see the trend.

Also just noticed that final answer can be simplified to:

x = 28275625 * e ^ (1 / ( (n * 17) + 7 ) )

However this does not use the hint at all or even give nice numbers so I don’t think it is right.

x is the 7th root of 28274625. Or the 24th root, or the 41st root etc. In other words 11.600…, 2.043…, and so on.

E.g. expressed in logs to base 11.600, 28274625 is 7, because raising 11.600 to the power 7 gives you 28274625.

But it’s an odd-looking equation and a series of answers like that isn’t useful in all situations. Which makes me curious - what’s the context? Where does it come from? What does x represent? Are you sure the working up to where you got this equation is right? :smiley:

This is for calculating the reverse multiplicative modulo inside an RSA encryption function , a step by step thing is what im looking for.

I think that quew8 answer is correct. You might want to have a look at:


and
http://www.mathsisfun.com/sets/injective-surjective-bijective.html
As modulo isnt an injective operation you dont get one solution, you get a set.
You could also go for:

a = log x (b) % c
(n*c)+a= log x (b)
d:=(n*c)+a
d = log x (b)
b = x^(d)
-> x = b^(1/d) //d != 0

I hope that I didnt make a mistake, it has been a long day :slight_smile:
Anyways, I would go for the solution quew8 already posted as you can work with the ln much better then with log. ln has some nice features, for example the power series:

Edit:

As written above, keep in mind that modulo isnt injective. You will get the x that solves the equation and that you used to generate it, BUT you wont know what the “correct” x out of your set is.
No offense/dont want to be rude/just a hint, you might want to have a look at some more advanced math before implementing your own RSE :slight_smile:

You might want to read the posts properly :wink:

Our answers were the same (11.6, 2.04 etc), except quew8 went an absurdly long way round. There’s no need to invoke any change of base - there is no original base to even change from - that’s what we’re trying to find! Just expand the modulo 17 integer series and take roots.

for (double i = 7; i < 100; i += 17) {
   System.out.println(Math.pow(28274625, 1/i));
}
11.60072855340886
2.043971655118861
1.519642344862726
1.3442262113481696
1.2570482797273588
1.2050177497618415

But I do agree with you self-coding an RSA routine is for people way brainier than us game developers :slight_smile: As you pointed out this seems unlikely to be the right way to do it anyway, because it generates a series.

I totally missunderstood your answer, ::slight_smile:
thought that your post

refers to the post from quew8.
That’s why I wrote the math step by step :slight_smile:

No excuse but I knew that I was doing something wrong ;D

My bad, I should prob use the quote button more!

So, the objective is to crack RSA? Whoever gave you this assignment was messing with you.

No not to crack it , I was just attempting to see how to derive to try and further understand how the functions actually work. It’s an interesting topic that is very useful these days.