tag:blogger.com,1999:blog-53443658286292612992024-03-09T03:20:54.417+05:30INTEGER PROPERTIESKadhirvel Polymath+919790890221http://www.blogger.com/profile/09558021274736211643noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-5344365828629261299.post-59731783824348713902015-03-05T11:35:00.001+05:302015-03-05T11:35:33.330+05:30Euler's Totient Function of Odd Composite<div dir="ltr" style="text-align: left;" trbidi="on">
<span style="background-color: white; color: #404040; font-family: Roboto, arial, sans-serif; font-size: 13px; line-height: 18.2000007629395px;">Let 'N' be any odd composite. </span><br style="background-color: white; color: #404040; font-family: Roboto, arial, sans-serif; font-size: 13px; line-height: 18.2000007629395px;" /><br style="background-color: white; color: #404040; font-family: Roboto, arial, sans-serif; font-size: 13px; line-height: 18.2000007629395px;" /><span style="background-color: white; color: #404040; font-family: Roboto, arial, sans-serif; font-size: 13px; line-height: 18.2000007629395px;">Find semi-prime Sp = uv such that </span><br style="background-color: white; color: #404040; font-family: Roboto, arial, sans-serif; font-size: 13px; line-height: 18.2000007629395px;" /><br style="background-color: white; color: #404040; font-family: Roboto, arial, sans-serif; font-size: 13px; line-height: 18.2000007629395px;" /><span style="background-color: white; color: #404040; font-family: Roboto, arial, sans-serif; font-size: 13px; line-height: 18.2000007629395px;">(2u+1)(2v+1) <= N <= 3(2Sp+1). or N <= (2u+1)(2v+1) < 3(2Sp+1)</span><br style="background-color: white; color: #404040; font-family: Roboto, arial, sans-serif; font-size: 13px; line-height: 18.2000007629395px;" /><br style="background-color: white; color: #404040; font-family: Roboto, arial, sans-serif; font-size: 13px; line-height: 18.2000007629395px;" /><span style="background-color: white; color: #404040; font-family: Roboto, arial, sans-serif; font-size: 13px; line-height: 18.2000007629395px;"> [[ For example let N = 65 then required semi-prime is 14 = 2*7 such that 65 < (2*2 + 1)(2*7 +1) < 3*(2*14 + 1) i.e., 65 < 5*15 < 3*29 i.e., 65 < 75 < 87]]</span><br style="background-color: white; color: #404040; font-family: Roboto, arial, sans-serif; font-size: 13px; line-height: 18.2000007629395px;" /><span style="background-color: white; color: #404040; font-family: Roboto, arial, sans-serif; font-size: 13px; line-height: 18.2000007629395px;">{{ Note: Finding Semi-prime Sp will be optimized through Trial & Error }}</span><br style="background-color: white; color: #404040; font-family: Roboto, arial, sans-serif; font-size: 13px; line-height: 18.2000007629395px;" /><br style="background-color: white; color: #404040; font-family: Roboto, arial, sans-serif; font-size: 13px; line-height: 18.2000007629395px;" /><span style="background-color: white; color: #404040; font-family: Roboto, arial, sans-serif; font-size: 13px; line-height: 18.2000007629395px;">Let Lsp be any semiprime nearer and lesser than Sp compared to other.</span><br style="background-color: white; color: #404040; font-family: Roboto, arial, sans-serif; font-size: 13px; line-height: 18.2000007629395px;" /><br style="background-color: white; color: #404040; font-family: Roboto, arial, sans-serif; font-size: 13px; line-height: 18.2000007629395px;" /><span style="background-color: white; color: #404040; font-family: Roboto, arial, sans-serif; font-size: 13px; line-height: 18.2000007629395px;">Then Euler's Totient function Phi(N) = 4*(Sp - k) where 0 <= k <= (Sp - Lsp).</span><br style="background-color: white; color: #404040; font-family: Roboto, arial, sans-serif; font-size: 13px; line-height: 18.2000007629395px;" /><br style="background-color: white; color: #404040; font-family: Roboto, arial, sans-serif; font-size: 13px; line-height: 18.2000007629395px;" /><span style="background-color: white; color: #404040; font-family: Roboto, arial, sans-serif; font-size: 13px; line-height: 18.2000007629395px;">[[ For example for 65 = 5*13 Phi(65) = 4*12 = 48 = 4*(14-2) Look above example Sp = 14, Lsp = 9, Sp - Lsp = 14-9 = 5; here we saw that 0 < k < 5]]</span></div>
Kadhirvel Polymath+919790890221http://www.blogger.com/profile/09558021274736211643noreply@blogger.com0tag:blogger.com,1999:blog-5344365828629261299.post-20918159281326068672015-02-02T08:58:00.000+05:302015-03-05T12:21:29.700+05:30Odd Composite Special Case Property<div dir="ltr" style="text-align: left;" trbidi="on">
Let 'N' be any odd composite with factors 'p' & 'q'. Then there exist following property for many odd composites S^2 = y^2(mod p) = (y + 1)^2(mod q),<br />
<div style="background-color: white; color: #222222; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 22px;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 22px;">
Where</div>
<div style="background-color: white; color: #222222; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 22px;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 22px;">
S = Floor(Sqrt(2N+4)) or Ceiling(Sqrt(2N+4)) </div>
<div style="background-color: white; color: #222222; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 22px;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 22px;">
such that Floor(Sqrt((N+2)^2 - S^2)) = N and </div>
<div style="background-color: white; color: #222222; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 22px;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 22px;">
Floor(Sqrt((N+2)^2 - (S-1)^2)) = N +1, </div>
<div style="background-color: white; color: #222222; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 22px;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 22px;">
Then calculate k = 4N+4-(S^2), </div>
<div style="background-color: white; color: #222222; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 22px;">
y = Floor(Sqrt(abs[(2N-k)- S])), </div>
<div style="background-color: white; color: #222222; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 22px;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 22px;">
Therefore using 'S' & 'y' we can factorize 'N' such that</div>
<div style="background-color: white; color: #222222; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 22px;">
p = GCD([S^2-y^2], N) & </div>
<div style="background-color: white; color: #222222; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 22px;">
q =GCD([S^2-(y+1)^2], N).<br />
<br />
<br />
<div style="color: #3f3f3f; font-family: 'Helvetica Neue', Helvetica, Arial, san-serif, Roboto; font-size: 13px; line-height: 16px; margin: 0px; padding: 0px;">
{For example. N = 132289 = 263*503,</div>
<div style="color: #3f3f3f; font-family: 'Helvetica Neue', Helvetica, Arial, san-serif, Roboto; font-size: 13px; line-height: 16px; margin: 0px; padding: 0px;">
S = Ceiling(Sqrt((2*132289)+4)) = 515, </div>
<div style="color: #3f3f3f; font-family: 'Helvetica Neue', Helvetica, Arial, san-serif, Roboto; font-size: 13px; line-height: 16px; margin: 0px; padding: 0px;">
k = (4*132289)+4-(515^2) = 263935, </div>
<div style="color: #3f3f3f; font-family: 'Helvetica Neue', Helvetica, Arial, san-serif, Roboto; font-size: 13px; line-height: 16px; margin: 0px; padding: 0px;">
then it is found that</div>
<div style="color: #3f3f3f; font-family: 'Helvetica Neue', Helvetica, Arial, san-serif, Roboto; font-size: 13px; line-height: 16px; margin: 0px; padding: 0px;">
S^2 = 515^2 = 11^2(mod 263) = (11+1)^2(mod 503) here y = 11 = Floor(Sqrt([(2*132289)-263935]<wbr></wbr>-515). }</div>
<div style="color: #3f3f3f; font-family: 'Helvetica Neue', Helvetica, Arial, san-serif, Roboto; font-size: 13px; line-height: 16px; margin: 0px; padding: 0px;">
<br /></div>
<div style="color: #3f3f3f; font-family: 'Helvetica Neue', Helvetica, Arial, san-serif, Roboto; font-size: 13px; line-height: 16px; margin: 0px; padding: 0px;">
<br /></div>
<div style="color: #3f3f3f; font-family: 'Helvetica Neue', Helvetica, Arial, san-serif, Roboto; font-size: 13px; line-height: 16px; margin: 0px; padding: 0px;">
<span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8000001907349px; line-height: normal;">For some other numbers S = Floor(√(4N+4)) or S = Floor(√(2N+4) and y = Floor(√(k-S)) or nearer to it.</span><br />
<br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8000001907349px; line-height: normal;" />
<span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8000001907349px; line-height: normal;">{For example. N = 1091501 = 523*2087,</span><br />
<span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8000001907349px; line-height: normal;"> S = Floor(√((2*1091501)+4)) = 2089,</span><br />
<span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8000001907349px; line-height: normal;">k = (4*1091501)+4-(2089^2) = 2087,</span><br />
<span class="im" style="color: #500050; font-family: arial, sans-serif; font-size: 12.8000001907349px; line-height: normal;">then it is found that</span><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8000001907349px; line-height: normal;"> S^2 = 2089^2 = 2^2(mod 2087) = (2+1)^2(mod 523) here y = 2 = √(S-k)+1 =√(2089-2087)+1}</span></div>
</div>
</div>
Kadhirvel Polymath+919790890221http://www.blogger.com/profile/09558021274736211643noreply@blogger.com0tag:blogger.com,1999:blog-5344365828629261299.post-86931087664523526552013-01-14T08:50:00.000+05:302013-01-14T08:50:11.169+05:30Odd Semi-prime Property <br />
<span style="font-family: arial; font-size: x-small;">Let N = pq be any odd semiprime. Let 's' be the ceiling of square root of 'N'.</span><br />
<span style="font-family: arial; font-size: x-small;">If 's' is even then there exist odd 'l' and k = l + 2 such that (s^2 - k^2) < N < (s^2 - l^2) else</span><br />
<span style="font-family: arial; font-size: x-small;">If 's' is odd then there exist even 'l' and k = l + 2 such that (s^2 - k^2) < N < (s^2 - l^2)</span><br />
<span style="font-family: arial; font-size: x-small;"><br /></span>
<span style="font-family: arial; font-size: x-small;">Let r = q + Δ,</span><br />
<span style="font-family: arial; font-size: x-small;"> where 'Δ' is very small +ve integer compared to 'p' & 'q'</span><br />
<span style="font-family: arial; font-size: x-small;"><br /></span>
<span style="font-family: arial; font-size: x-small;">When 2l + 4 < p then pr will be less than and nearer to (s^2 + l^2) and p(r + 1) will be greater than and nearer to (s^2 + k^2)</span><br />
<span style="font-family: arial; font-size: x-small;"><br /></span>
<span style="font-family: arial; font-size: x-small;"><br /></span>
<span style="font-family: arial; font-size: x-small;">When 2l + 4 > p then pr will be greater than and nearer to (s^2 + l^2) and depends upon 2p, p(r + 1) will be either greater or lesser than and nearer to (s^2 + k^2)</span><br />
Kadhirvel Polymath+919790890221http://www.blogger.com/profile/09558021274736211643noreply@blogger.com0tag:blogger.com,1999:blog-5344365828629261299.post-40760962194835532922013-01-08T04:32:00.001+05:302013-01-08T04:58:47.490+05:30Odd Composite PropertyLet N = pq be any odd composite. Let k = 1, 2, 3, ...., p, ...., q, ... n. Let u = (N- 1)/2 & v = u +1. Let x = u^2(mod k) and y = v^2(mod k). Then | x - y | = 0 when k = p or k = q else | x - y | != 0. Let p(r -1) < u^2 < pr where r is some integer and let ps < v^2 < p(s + 1) where s is some integer then s - r = q - 1 or s - r = q - 3.<br />
Example 161 = 7*23, here u (161 -1)/2 = 80, v = 81, 80^2 = 2(mod 7) = 6(mod 23), 81^2 = 2(mod 7) = 6(mod 23). 7*914 < 80^2 < 7*915 and 7*937 < 81^2 < 7*938, 937 - 915 = 22 = 23 -1.Kadhirvel Polymath+919790890221http://www.blogger.com/profile/09558021274736211643noreply@blogger.com0tag:blogger.com,1999:blog-5344365828629261299.post-25278210906313031012012-11-22T23:42:00.000+05:302016-11-03T20:28:44.327+05:30Fermat's Factorization Running Time<div dir="ltr" style="text-align: left;" trbidi="on">
<b>Let N = pq is any odd composite. Let d = 2n be the difference between the two closest factors of 'N'. </b><span style="font-size: x-small;">( For e.g., 105 = 3x35 = 5x21 = 7x15
here 15 and 7 is close to each other compare to other. Therefore d = 15 - 7 = 8 therefore n = d/2 = 4 )</span>. <b>Let 's' be the floor value of square root of 'N'. Let N = a^2 - b^2 be the Fermat factorization of N. In order to attain best case scenario a - s <= 2 following are the required condition for factors of N. I call these factors as Best Fermat Factors.</b><br />
<br />
<u><b>Case1: If 'n' is odd then p should be (n(n-4) + 7)/4 and q should be (n(n+4) + 7)/4</b></u><br />
<b><u><br /></u>
<u>Case2: If 'n' is even & m = n/2 is odd then p should be (m(m -2) + 2) and q should be (m(m + 2) + 2)</u></b><br />
<b><u><br /></u>
<u>Case3: If 'n' is even & m = n/2 is also even then p should be (m - 1)^2 and q should be (m + 1)^2</u></b><br />
<br />
(<span style="background-color: red;">Note</span>: Try the practical testing using any numbers even very big numbers then you can understand my ideas. I used the smaller numbers as an inductive proof for simplicity. Please read the 3 cases and its note point. May be explanations won't be in a polished way, please adjust.)<br />
<br />
<br />
Case 1: Explanation Below<br />
Example1. let d = 2x9 here n = 9 is odd then p = (9x5 + 7)/4 = 13 & q = (9x13 + 7)/4 = 31 Therefore N = 13x31 = 403 = 22^2 - 9^2 and floor value of sqare root of 403 is 20, here a = 22 & s = 20 and a -s = 2.<br />
<br />
<u>Note: </u><br />
Here p = 13 and q = 31 for the given d = 2x9 running time complexity is 2 for Fermat factorization. The other set of factors with same difference like (11, 29), (9, 27)..... (3, 21) the running time complexity will increase gradually and worst case will occur. And the few set of factors greater than p and q with same difference like (15, 33), (17, 35)... will remain same time complexity for Fermat factorization. Let M = rs where s - r = q - p (where q and p are best Fermat factors) and r < p and s < q then time complexity will increase compared to N = pq. For e.g., 11x29 = 319 = 20^2 - 9^2 floor of square root of 319 is 17. Now 20 - 17 = 3 complexity increased compared to Best Fermat factors (13, 31)<br />
<br />
<br />
<u>Case2: </u>Explanation<u> Below</u><br />
Example2. let d = 2x14 here n = 14 is even and m = n/2 = 7 is odd then p = 7*5 + 2 = 37 and q = 7*9 + 2 = 65 Therefore N = 37x65 = 2405 = 51^2 - 14^2 and floor value of square root of 2405 is 49, here a = 51 & s = 49 and a -s = 2.<br />
<br />
<u>Note: </u><br />
Here p = 37 and q = 65 for the given d = 2x14
running time complexity is 2 for Fermat factorization. The other set of
factors with same difference like (35,63), (33,61)..... (3, 31) the
running time complexity will increase gradually and worst case will occur. And the few set of factors
greater than p and q with same difference like (39,67), (41,69)...
will remain same time complexity for Fermat factorization.<br />
<br />
<u>Case3: </u>Explanation<u> Below</u><br />
Example3. let d = 2x16 here n = 16 is even and m = n/2 = 8 is even then p = (8-1)^2 = 49 and q = (8 + 1)^2 = 81 Therefore N = 49x81 = 3969 = 65^2 -
16^2 and floor value of square root of 3969 is 63, here a = 65 & s = 63 and a -s = 2.<br />
<br />
<u>Note: </u><br />
Here p = 49 and q = 81 for the given d = 2x16
running time complexity is 2 for Fermat factorization. The other set of
factors with same difference like (47,79), (45,77)..... (3, 35) the
running time complexity will increase gradually and worst case will occur. And the few set of factors
greater than p and q with same difference like (51,83), (53,85)...
will remain same time complexity for Fermat factorization.<br />
<br />
<u>Conclusion: </u><br />
Hence irrespective of the difference there exist Best Fermat Factors, so that factorization complexity is easy. The logic that odd composite with least difference will be factored easily and large difference would factored hardly is wrong. Hardness is depends upon the how much the factors are deviated from the Best Fermat Factors. And i had a new methodology to factorize the given number based on above properties.</div>
Kadhirvel Polymath+919790890221http://www.blogger.com/profile/09558021274736211643noreply@blogger.com0tag:blogger.com,1999:blog-5344365828629261299.post-39057523885604294732008-07-28T12:11:00.000+05:302013-01-15T09:05:51.781+05:30Hi EveryoneWelcome to the Fantasy of Numbers. This page reveals my own discoveries on Number Theory. Sorry if something i re-introduced which i unaware of.Kadhirvel Polymath+919790890221http://www.blogger.com/profile/09558021274736211643noreply@blogger.com0