Number of try for $p$ and $q$ to find $m$(Brute-force a RSA key)

Question

To find $m$ there is a method called Brute-force that calculates all possible combination and apply them to find the only one true answer.

This is an example:

Prime number (Bitsize: 512) (*): p ============================================================= dec ==== 13059313724319126815698328933761111023445599295666419531591666294317326706135802771868772964777544791631665594397048785390359533210057462940524389248589953

Prime number (Bitsize: 512) (*): q ============================================================= dec ==== 11292070857539789665049405958629835091255215659291199773104193934768436659737674012016529740997052319915770253093741328930874356021224885805564002892313913

Modulus (Bitsize: 1024): n=p*q ============================================================= hex ==== d1ffe2398f9c81edb18b3a94a59939e54c751961c27c6e377d55b1c6477a6b88d7404d9f2dcad2928b6058d1f63339cb63ab9e48c0882ca55a044719ab304edd30811ad743aefaeb5d1576685e58808635d8837c7bc097343cddb21f88d72c3b7cc4a6b45a5f0e5214844a1ef88decec9c0780b513772e64d0cadad3161571b9

looking for a mathematical formula to estimate the number of entire test values.

Answer 1

In a brute force trial you are simply taking $m$, guessing $p$ and dividing to see if it comes out even. If you know nothing about how $p$ and $q$ are chosen, you need to try all the primes up to $\sqrt m$, which is about $\frac 12\cdot \frac {\sqrt m}{\log m}$. Traditionally we force $p$ and $q$ to be just about the same size, so you can reduce this a bit but not much, say $10\%$

If $m$ has $1024$ bits it is about $2^{1024} \approx 1.8\cdot 10^{308}$. There are about $2^{512} \approx 1.3\cdot 10^{154}$ choices for $p$. If you had an oracle to tell you which of these are prime, it is about $1$ in $355$ of them, so that would cut the number to try to about $3.8 \cdot 10^{151}$. You are not going to get this done any time soon.