If I have the following number, called n: 95789475894946344480971579557266277535799700804994840267140205584908768904895768948590485961900214653419480471608575222628934671405734092147743953303897316683406873623402076894361066482026698747269194533568241380908198579649362123303511284937304748452871420978357485793030284954802940809309474904948944096953
and this n is, firstly, going to be multiplied z many times and, secondly, z x n is divided by the following divisor: 258732191050391204174482508661063007579358463444809715795726627753579970080749948404278643259568101132671402056190021464753419480472816840646168575222628934671405739213477439533870489791038973166834068736234020361664820266987726919453356824138007381985796493621233035112849373047484148339095287142097834798153
and, thirdly, I know that the remainder I am seeking is the following number: 5789475894946344480971579572662775758908698579584974935799700804994840427864325956810113267140205584908768904895768948590485961900214653419480471608575222628934671405734092147743953387048979103897316683406873623465789384057098302076894361664820266987472691945335682413809081985796493303511284937304748414539
and fourthly, n and the divisor are co-prime,
Then what is z?
If the largeness of the numbers is confusing then let me just example what I am seeking to ask with smaller numbers:
If I have the number 73 and firstly, this 73 is going multiplied z many times and then, secondly, z x 73 is going to be divided by 97 and, thirdly, I know that the remainder form this division is 56, and fourthly, n=73 and divisor=97 are co-prime. then what is z?
The answer is 30. To verify:
73 x 30 = 2190 and 2190 mod 97 = 56.
I can just calculate multiples of 73 from 1 to 96 and write each product in a computer spreadsheet cell in succeeding rows and then at each row the product is divided by 97. At the 30th row I will see that the remainder is 56. It is easy because the numbers are small.
I can't count up to rows to a value that is over 300 digits long. Even in a thousand years I won't get the answer this way, even if I had a super-computer.
So ultimately the question is: What algorithm can I use to reduce the search time down to under 1 minute?
I do know that for other things such as large modular multiplicative inverses, even when the numbers are over 300 digits, the modular inverse can be found in less than 3 seconds using the Extended Euclidean algorithm using a standard desktop home computer that has a i3 intel microchip processor. So, Is there something like the Extended Euclidean algorithm that I can use to find the z multiple of number n when working with very large integers?
Teach me. I want to learn it.