A random relative prime number based on the modulus
What is m.bitLength, and how often do you get a &lt;= 0 or an gcd-1? 

Why do you think creating an object in the loop could be bad? Performance? Memory wise? 

An object is ready for garbage collection as soon as it is unreachable and out of scope. 

So the second object, if the first one fits the condition, will hide the first one - the first one is out of scope, and unreachable. 

For a cheap object like a BigInteger, you may worry if you produce millions and millions of Objects in one second, over and over again. Maybe then, if you experience a performance problem, you can measure and find out, where it happens.