You’ve got it the wrong way around
The first argument is what you want to rewrite from, and the second argument is what you want to rewrite to.
With a sidenote that you can’t put query parameter in the first argument, you have to use a RewriteCond for that.
RewriteEngine On
RewriteCond %{QUERY_STRING} search=&submit=search&page=(\d+)
RewriteRule ^index\.php$ /page/%1? [L]
%1 will insert the digit captured in the RewriteCond by (\d+). The ? at the end of the new URL is to tell Apache not to re-append the original query string. Otherwise it would become /page/1?search=&submit=search&page=1.
You said it wrong (as Rémon stated) but your code is okay. I’d prefer that the $1 regex replace the * with + to require at least one character but it should work as is.
Are you sure that mod_rewrite is enabled? It must be because you’re not getting a 500 error. What else is in your .htaccess which might interfere with this code?